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)$


Comment