题目描述
从数组中选择3不同的数,使得nums[1]+nums[2]+nums[3]==0;
样例
算法1
时间复杂度 O(n2)
方法: 排序+双指针
1)去重的问题,只需要枚举相同一段数的第一个即可
2) 先循环枚举 nums[i]+nums[j] 当这位一个数下标是j, 找另一个数,使得 nums[]+nums[]+x==0;
单调性:当nums[]+nums[]+x>0,只有x变小才可能等于0
当 nums[]+nums[]+x<0,只能nums[]+nums[]变大才有可能
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
sort (nums.begin(),nums.end());
int k = nums.size()-1;
for (int i = 0;i<nums.size();i++)
{
for (int j = i+1;j<nums.size();j++)
{
while (k>j&&nums[i]+nums[j]+nums[k]>0) k--;
if (nums[i]+nums[j]+nums[k]==0) res.push_back({nums[i],nums[j],nums[k]});
}
}
return res;
}
};