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;}
};