LeetCode 15 三数之和

题目链接

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

题目解析

        // 1. 排序+双指针

        // 2. 固定一个值nums[i] 然后去剩下的位置去找 两数之和符合nums[j]+nums[k]是否等于-nums[i]

        // 3. 细节问题：由于题目中是不可以包含重复的三元组的，因此我们需要对我们所选的三个数进行去重

代码

class Solution 
{
public:vector<vector<int>> threeSum(vector<int>& nums) {// 1. 排序+双指针// 2. 固定一个值nums[i] 然后去剩下的位置去找 两数之和符合nums[j]+nums[k]是否等于-nums[i]// 3. 细节问题：由于题目中是不可以包含重复的三元组的，因此我们需要对我们所选的三个数进行去重int n=nums.size();sort(nums.begin(),nums.end());vector<vector<int>> vv;vector<int> v;for(int i=0;i<n;){int target=-nums[i];// 由于数组中的数据是升序的// 那么最小的数都是正数，那么后面的数都是正数// 因此就不可能会有三个数相加等于0if(nums[i]>0) break; // 当该值不符合情况直接跳出for循环int left=i+1,right=n-1;while(left<right){int sum=nums[left]+nums[right];if(sum<target){left++;}else if(sum>target){right--;}// 当走到该位置的时候，那么这三个数就是符合条件的else{v.clear();v.push_back(nums[i]); v.push_back(nums[left]); v.push_back(nums[right]);vv.push_back(v);// vv.push_back({nums[i],nums[left],nums[right]});left++;right--;// 对两个指针进行去重while(left<right&&nums[left]==nums[left-1]) left++;while(left<right&&nums[right]==nums[right+1]) right--;}}// 对当前固定值进行去重i++;while(i<n&&nums[i]==nums[i-1])  i++;}return vv;}
};