题目要求
解题思路
这道题我们可以使用暴力解法来解决,时间复杂度为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;}
};