【力扣】15.三数之和

AC截图

题目

思路

这道题如果简单的用暴力三重遍历去做，会超时。所以我们思考假如有三个下标，i，l，r

其中i=0（初始），l=i+1 r=nums.size()-1

我们固定nums[i]的值，那么就转换为两数之和，我们需要找到nums[l]+nums[r]==-nums[i]

假如我们对数组排序，那么记target=-nums[i],sum=nums[l]+sum[r]

①如果sum==target，即为所求,l++,r--

②如果sum<target，为了得到更大的sum，只能l++

③如果sum>target，为了减小sum，只能r--

接下来，就是一些剪枝操作。比如数组中存在重复的数字，就需要跳过。

①假如已经有sum==target并且进行了l++,r--

此时如果存在与sum[l]或者sum[r]相同的值，必然得到的是相同的数组，就需要使用l++或者r--跳过

②如果出现了num[i]值重复，由于上一个循环已经得到了所有的序列，此时也应给使用continue跳过

代码

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;

        sort(nums.begin(),nums.end());

        for(int i=0;i<nums.size();i++){
            if(i>0 && nums[i]==nums[i-1]) continue;
            int l=i+1;
            int r=nums.size()-1;
            int target = -nums[i];
            while(l<r){
                int sum = nums[l]+nums[r];
                if(sum==target){
                    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--;
                    }
                }else if(sum>target){
                    r--;
                }else{
                    l++;
                }

            }
        }
        return res;
    }
};