双指针 Leetcode 15 三数之和
Leetcode 15
学习记录自代码随想录
要点:1、如果用哈希表则在处理输出数组去重时较复杂;
2、双指针法,双指针法使用前要对数组排序。
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
// map<int, int> nums_map;
vector<vector<int>> res;
// 双指针
// 排序,双指针多要排序
sort(nums.begin(), nums.end(), [](int& a, int& b){return a < b;});
for(int i = 0; i < nums.size(); i++){
if(nums[i] > 0) return res;
// 去重第一个数
if(i > 0 && nums[i] == nums[i-1]) continue;
int left = i+1;
int right = nums.size()-1;
while(left < right){
if(nums[i] + nums[left] + nums[right] < 0){
left++;
}else if(nums[i] + nums[left] + nums[right] > 0){
right--;
}else{
res.push_back({nums[i], nums[left], nums[right]});
// 去重第二个,第三个数
while(left < right && nums[left+1] == nums[left]) left++;
while(left < right && nums[right-1] == nums[right]) right--;
left++;
right--;
}
}
}
return res;
}
};