【LeetCode】15.三数之和

题目要求

解题思路

这道题我们可以使用暴力解法来解决，时间复杂度为O（N^3）。但是会超时，因此我们需要对暴力解法进行优化，而这道题我们使用双指针来进行优化，即依次固定一个数，在接下来的区间中找到两数之和等于固定数的相反数即可。还有一点需要注意：我们需要不重不漏的添加。

代码实现

class Solution 
{
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> ret;sort(nums.begin(),nums.end());int len=nums.size();int cur=0;while(cur<len){//当前的目标值int target=-nums[cur];//双指针法int left=cur+1,right=len-1;while(left<right){//相等时if(nums[left]+nums[right]==target){ret.push_back({nums[cur],nums[left],nums[right]});//所有情况，还得继续，并且值不能相同left++;while(left<right&&nums[left-1]==nums[left]){left++;}right--;while(left<right&&nums[right+1]==nums[right]){right--;}}//小于时else if(nums[left]+nums[right]<target){left++;}//大于时else{right--;}}cur++;while(cur<len&&nums[cur-1]==nums[cur]){cur++;}}return ret;}
};