【优选算法】7----三数之和

来了来了，他来了，又是学习算法的一天~

今天的嘉宾是中等难度的算法题----三数之和！

------------------------------------------begin------------------------------------

题目解析：

哇趣！又是给了一个数组，又是需要我们在一个数组中进行操作，但这次不是二元那么简单了，而

是三元~

讲解算法原理：

方法一：肯定还是暴力解法啦，直接三个for循环编译，时间复杂度直接爆炸，包不通过的~（所以

不推荐）

方法二：基于暴力算法，我们才可以进行优化算法，还是需要我们的老朋友left和right指针来进行

编译，同样我们需要多加一个对象来固定一个数，题目要求三数相加为0，所以我们可以定义一个

target来取所固定的相反数来与left和right位置的值的和来进行比较，判断~

编写代码：

class Solution 
{
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>>ret;sort(nums.begin(),nums.end());int n=nums.size();for(int i=0;i<n;){if(nums[i]>0){break;}int left=i+1,right=n-1,target=-nums[i];while(left<right){int sum=nums[left]+nums[right];if(sum>target){right--;}else if(sum<target){left++;}else{ret.push_back({nums[i],nums[left],nums[right]});right--;left++;while(left<right&&nums[right]==nums[right+1]){right--;} while(left<right&&nums[left]==nums[left-1]){left++;}}}i++;while(i<n&&nums[i]==nums[i-1]){i++;}}return ret;}
};

题目还是有点复杂的，不过多画图还是有用的哦~

题目直达->

15. 三数之和 - 力扣（LeetCode）

------------------------------------------end--------------------------------------