Given an array S of n integers, are there elements a, b, c in S 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.
For example, given array S = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
找数组中所有和为0的三元组,结果中不能有任何重复。排序后nums[i]作为最大元素的候选,在i元素前找和为-nums[i]的二元对,也就是2sum。2sum用首尾双指针。为了去除结果中重复的,2sum内判断当前指针后面是否为相同元素,是就说明当前值已经考虑过,跳。最外层的i同理,不过判断条件不能再是看前面i -1是否和nums[i]相同,因为这样会错误的把两个nums[i]作为解元素的情况刨除。
Copy /*
* @lc app=leetcode id=15 lang=cpp
*
* [15] 3Sum
*/
// @lc code=start
class Solution {
public :
vector < vector < int >> threeSum ( vector < int > & nums) {
const int N = nums . size ();
sort ( nums . begin () , nums . end ());
vector < vector <int>> res;
for ( int i = 2 ; i < N; ++ i) {
if (i < N - 1 && nums [i] == nums [i + 1 ]) continue ;
const int t = - nums [i];
for ( int j = 0 , k = i - 1 ; j < k;) {
if ( nums [j] + nums [k] < t || j > 0 && nums [j] == nums [j - 1 ]) {
++ j;
} else if ( nums [j] + nums [k] > t || k < i - 1 && nums [k] == nums [k + 1 ]) {
-- k;
} else res . push_back ({ nums [i] , nums [j ++ ] , nums [k -- ]});
}
}
return res;
}
};
// @lc code=end
Copy class Solution {
public List < List < Integer >> threeSum ( int [] nums) {
Arrays . sort (nums);
List < List < Integer >> res = new ArrayList <>();
for ( int i = 0 ; i < nums . length ; i ++ ) {
if (i > 0 && nums[i] == nums[i - 1 ]) {
continue ;
}
int target = - nums[i];
int l = i + 1 , r = nums . length - 1 ;
while (l < r) {
if (nums[l] + nums[r] < target) {
l ++ ;
} else if (nums[l] + nums[r] > target) {
r -- ;
} else {
res . add ( Arrays . asList (nums[i] , nums[l] , nums[r]));
l ++ ;
r -- ;
while (l < r && nums[l] == nums[l - 1 ]) {
l ++ ;
}
while (l < r && nums[r] == nums[r + 1 ]) {
r -- ;
}
}
}
}
return res;
}
}
O(N^2).