leetcode hot100刷题日记——37.三数之和

解答：
首先将nums进行排序，更方便做。
三元组三个数，可以看成如何取这三个数。
第一层循环：看着第一个数的指针。
第二层循环：看着第二个数的指针。
第三个数自然而然从数组的最后一个数字开始找满足-(num1+num2)的数字

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {int n=nums.size();sort(nums.begin(),nums.end());vector<vector<int>> ans;//i是第一个指针，指向三元组的第一个数for(int i=0;i<n;i++){//但是不能和之前的数相同，因为结果中不含有相同的三元组if(i>0&&nums[i]==nums[i-1]){continue;}//k指向三元组的第三个数int k=n-1;int target=-nums[i];//枚举三元组的第二个数for(int j=i+1;j<n;j++){// 需要和上一次枚举的数不相同if(j>i+1&&nums[j]==nums[j-1]){continue;}//需要保证第二个数在第三个数的左侧while(j<k&&nums[j]+nums[k]>target){--k;//如果后两个指针的和大于target，说明第三个数需要小一些}if(j==k){break;}if(nums[j]+nums[k]==target){ans.push_back({nums[i],nums[j],nums[k]});}}}return ans;}
};

时间复杂度：O(n^2)
空间复杂度：O(logn)(排序)