Leetcode 15. 三数之和(排序 + 双指针)
2021年3月3日 周三天气晴 【不悲叹过去,不荒废现在,不惧怕未来】
1. 题目简介
2. 题解(排序 + 双指针)
主要思路:排序 + 双指针,难点是如何去重。
算法流程如下:
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { sort(nums.begin(),nums.end()); vector<vector<int>> res; const int n = nums.size(); for(int i=0;i<n;++i){ // 特判(剪枝) if(nums[i]>0) return res; // 如果第一个元素重复,提前退出 if(i>0 && nums[i]==nums[i-1]) continue; int beg = i+1, end = n-1; while(beg<end){ if(nums[beg]+nums[end]==-nums[i]){ // 保存符合条件的三元组 res.push_back({ nums[beg],nums[end],nums[i]}); // *重点:对第二个和第三个元素进行去重 while(beg<end && nums[beg]==nums[beg+1]) ++beg; while(beg<end && nums[end]==nums[end-1]) --end; ++beg; --end; } else if(nums[beg]+nums[end]>-nums[i]) --end; else ++beg; } } return res; } };
参考文献
https://leetcode-cn.com/problems/3sum/solution/pai-xu-shuang-zhi-zhen-zhu-xing-jie-shi-python3-by/