之和(medium)"/>
[双指针]leetcode15:三数之和(medium)
题目:
题解:
代码如下:
class Solution {
public:// 思路:先排序,然后枚举并固定a,使用首尾指针寻找b cvector<vector<int>> threeSum(vector<int>& nums) {if(nums.size()<=2)return {};vector<vector<int>> res;sort(nums.begin(),nums.end());for(int i=0;i<nums.size()-2;++i){// 由于数组已排序,nums[i]为正数,nums[i]之后的数必定也为正数,相加之后的结果不会为0,所以直接返回res即可if(nums[i]>0)return res;// nums[i]对应的元素值已经枚举过了,不需要再次枚举了if(i>0&&nums[i]==nums[i-1])continue;// 首尾指针来寻找b cint l=i+1,r=nums.size()-1;while(l<r){int sum=nums[i]+nums[l]+nums[r];if(sum>0)r--;// sum太大,向左逼近else if(sum<0)l++;// sum太小,向右逼近else {res.push_back({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;}
};
更多推荐
[双指针]leetcode15:三数之和(medium)
发布评论