题目描述
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.
Example1:
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
Note:
- The solution set must not contain duplicate triplets.
解题思路
- 暴力会出现TLE错误，
- 类似于2Sum的思路，首先排序，遍历这个排序的数组
- 访问第i个元素，然后设置begin，end两个指针，begin指针指向nums[i]的后一个元素，end指向数组的末尾
- 注意需要判断是否会有重复元素，重复元素跳过即可
- 两个地方需要判断
- 遍历这个数组的时候，需要判断nums[i],nums[i - 1],即当前元素是否已经上次循环中判断过了
- 如果找到nums[i] + nums[begin] + nums[end]这一个结果时，需要移动begin，end指针，这时候也需要判断，begin的后一个元素是否与当前元素重复，end的前一个元素是否与当前元素重复，如果是，需要先移动begin，end的位置
- 找到一个结果后，begin往前移一个，同时end往后移动一个；否则如果当前结果要比target大，end往前移动；当前结果比target小，begin往前移动。
C++代码
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
sort(nums.begin(), nums.end());
if(nums.size() == 0 || nums.back() < 0 || nums.front() > 0 || nums.size() < 2){
return {};
}
for(int i = 0; i < nums.size() - 2; i++){
if(nums[i] > 0){
break;
}
if(i > 0 && nums[i] == nums[i - 1]){
continue;
}
int begin = i + 1;
int end = nums.size() - 1;
int target = 0 - nums[i];
while(begin < end){
if(nums[begin] + nums[end] == target){
vector<int> t;
t.push_back(nums[i]);
t.push_back(nums[begin]);
t.push_back(nums[end]);
res.push_back(t);
while(begin < end && nums[begin] == nums[begin + 1]){ // Determine if there are duplicates
begin++;
}
while(begin < end && nums[end] == nums[end - 1]){ // Determine if there are duplicates
end--;
}
begin++;
end--;
}else if(nums[begin] + nums[end] > target){
end--;
}else{
begin++;
}
}
}
return res;
}
};
20200207解题思路
- 关键是如果去除重复元素的问题
- 这个题的思路可以转换为 定位一个元素，然后求target的问题
- 首先先排序
- 排完序后，在遍历这个元素的时候，就要找到这个元素的所有可能组合
- 这样如果后面有相同的元素，就直接选择跳过就可以
- 遍历这个元素，如果找到相等等于target元素时，这时候要检查,两个指针的位置是否会指向重复元素。即要有一个循环，从这个元素开始扫描，如果 nums[begin] == nums[begin + 1], 那么begin应该继续累加，同理，nums[end] == nums[end - 1], end将继续减少，最后在同时移动指针，begin指针，end指针
