Reference: LeetCode
Difficulty: Medium

Problem

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

  • The solution set must not contain duplicate triplets.
  • Elements are not necessarily unique.
  • Each element is only used once.

Example: 

1
2
3
4
5
6
Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is: [
  [-1, 0, 1],
  [-1, -1, 2]
]

Follow up: Reduce to $O(N^2)$ time complexity.

Analysis

Brute-Force

Two Issues:

  • Used Each Element Once: Solve by j = i + 1 and k = j + 1.
  • No Duplicate Triplets: Solve by if (i > 0 && nums[i] == nums[i - 1]) continue;.

Note: Use Arrays.asList(nums[i], nums[j], nums[k]) to make a new list quickly.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public List<List<Integer>> threeSum(int[] nums) {
  int n = nums.length;
  List<List<Integer>> result = new ArrayList<>();
  Arrays.sort(nums); // sort
  
  for (int i = 0; i < n; ++i) {
    if (i > 0 && nums[i] == nums[i - 1]) continue; // skip
    for (int j = i + 1; j < n; ++j) {
      if (j > i + 1 && nums[j] == nums[j - 1]) continue; // skip
      for (int k = j + 1; k < n; ++k) {
        if (k > j + 1 && nums[k] == nums[k - 1]) continue; // skip
        if (nums[i] + nums[j] + nums[k] == 0) {
          result.add(Arrays.asList(nums[i], nums[j], nums[k]));
        }
      }
    }
  }
  return result;
}

Time: $O(N^3)$
Space: $O(1)$

Two Pointers

  • Sort first.
  • For each element nums[i], use modified two-pointer approach.
    • When nums[j] + nums[k] == target:
      • Update j and k both.
      • Add two while-loop to handle Issue #2.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public List<List<Integer>> threeSum(int[] nums) {
  int n = nums.length;
  List<List<Integer>> result = new ArrayList<>();
  Arrays.sort(nums); // sort
  
  for (int i = 0; i < n; ++i) {
    if (i > 0 && nums[i] == nums[i - 1]) continue;  // skip same result
    // two pointers
    int j = i + 1, k = n - 1;  
    int target = -nums[i];
    while (j < k) { // each element is only used once
      if (nums[j] + nums[k] < target) {
        ++j;
      } else if (nums[j] + nums[k] > target) {
        --k;
      } else {
        result.add(Arrays.asList(nums[i], nums[j], nums[k]));
        ++j;
        --k;
        while (j < k && nums[j] == nums[j - 1]) j++;  // skip same result
        while (j < k && nums[k] == nums[k + 1]) k--;  // skip same result
      }
    }
  }
  return result;
}

Time: $O(N^2)$
Space: $O(1)$