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.
Example:
Given array nums = [-1, 0, 1, 2, -1, -4], A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]
Related Topics:
Array, Two Pointers
Similar Questions:
Sort the array in ascending order.
Pin the first number as A[i]. For the other two numbers, we can use two pointers to scan A[(i+1)..(N-1)], one from i+1 rightward, one from N-1 leftward.
// OJ: https://leetcode.com/problems/3sum/
// Author: github.com/lzl124631x
// Time: O(N^2)
// Space: O(1)
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& A) {
sort(begin(A), end(A));
vector<vector<int>> ans;
int N = A.size();
for (int i = 0; i < N - 2; ++i) {
if (i && A[i] == A[i - 1]) continue;
int L = i + 1, R = N - 1;
while (L < R) {
int sum = A[i] + A[L] + A[R];
if (sum == 0) ans.push_back({ A[i], A[L], A[R] });
if (sum >= 0) {
--R;
while (L < R && A[R] == A[R + 1]) --R;
}
if (sum <= 0) {
++L;
while (L < R && A[L] == A[L - 1]) ++L;
}
}
}
return ans;
}
};