Three Sum Problem
Description
LeetCode Problem 15. Given an array of integers nums, return all unique triplets (a, b, c) in the array which gives the sum of zero (a + b + c = 0).
Example:
1
2
Input: nums = [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 2], [-1, 0, 1]]
Solution
This problem is similar to the two sum problem.
Brute Force Approach
A simple solution is to use the brute force approach.
We loop through the array three times to get three different elements (a, b, c). Then we check whether (a + b + c = 0) is true or not.
If it is true, we add the triplets (a, b, c) to a set to ensure the final solutions do not contain duplicates; otherwise, we keep on searching.
The time complexity of this approach is O(n3), and the space complexity is O(n).
Two Pointer Approach
If the array is sorted, we can use the two pointer approach to reduce the time and space complexity.
We first sort the array in ascending order, the time complexity of this step is O(nlogn).
For each element nums[i] in the array, we set two pointers pointing to the elements larger than nums[i]: the left pointer l points to the smallest element on the right of nums[i], and the right pointer r points to the largest element on the right of nums[i].
We add the three numbers together (nums[i] + nums[l] + nums[r]) and compare it with 0.
If the sum is greater than 0, that means nums[r] is too big for the triplet (and nums[l] is already the smallest possible one), so we move the right pointer one step to the left (r-1) to try a smaller number.
If the sum is smaller than 0, that means nums[l] is too small for the triplet (and nums[r] is already the biggest possible one), so we move the left pointer one step to the right (l+1) to try a bigger number.
If the sum is 0, we find one solution and insert it into a set (to make sure the final solutions do not contain duplicates). Then we move the left pointer one step to the right (l+1), and the right pointer one step to the left (r-1). We move the left pointer one step to the right is because if we only move the right pointer and keep the left pointer pointing to the current number, the new nums[r] will be smaller or equal to the old nums[r]. If it is smaller, the sum of these three numbers will be less than 0. If it is equal, then this solution will be the same as the original one. Same reason applies to why we move the right pointer one step to the left.
Here is a complete walk-through of the approach.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| -1 | 0 | 1 | 2 | -1 | -4 | <-- (Original Array)
| -4 | -1 | -1 | 0 | 1 | 2 | <-- (Sorted Array)
i l r <-- (-4 + -1 + 2 = -3 < 0 => l++)
i l r <-- (-4 + -1 + 2 = -3 < 0 => l++)
i l r <-- (-4 + 0 + 2 = -2 < 0 => l++)
i l r <-- (-4 + 1 + 2 = -1 < 0 => l++)
i lr <-- (l=r -> i++)
i l r <-- (-1 + -1 + 2 = 0 => one solution found, l++, r--)
i l r <-- (-1 + 0 + 1 = 0 => one solution found, l++, r--)
i r l <-- (l>r => i++)
i l r <-- (-1 + 0 + 2 = 1 > 0 => r--)
i l r <-- (-1 + 0 + 1 = 0 => one solution found, l++, r--)
i r l <-- (l>r => i++)
i l r <-- (0 + 1 + 2 = 3 > 0 => r--)
i lr <-- (l=r => i++)
i lr <-- (l=r => i++)
i <-- (only one element left, return)
The time complexity can be reduced to O(n2), while the space complexity is still O(n).
Sample C++ Code
This is a C++ implementation of the two pointer approach.
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ans;
sort(nums.begin(), nums.end());
set<vector<int>> s;
int l, r;
for (int i = 0; i < nums.size(); i ++) {
l = i + 1;
r = nums.size() - 1;
while (l < r) {
int sum = nums[i] + nums[l] + nums[r];
if (sum == 0) {
s.insert({nums[i], nums[l], nums[r]});
l ++;
r --;
} else if (sum > 0) {
r --;
} else {
l ++;
}
}
}
for (auto x : s) {
ans.push_back(x);
}
return ans;
}
int main() {
vector<int> nums={-1, 0, 1, 2, -1, -4};
vector<vector<int>> ans;
ans = threeSum(nums);
for (int i = 0; i < ans.size(); i ++) {
for (int j = 0; j < ans[i].size(); j ++) {
cout << ans[i][j] << " ";
}
cout << endl;
}
}