LeetCode100.6 三数之和

对于这题，要直接三层循环的话复杂度太高，可以尝试排序后找到能与最大两个数相加为0的数，随后以此为起点进行双指针。注意忽略重复的数。这样复杂度就降为了O(n3)

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {sort(nums.begin(), nums.end());vector<vector<int>> ans;int n = nums.size();for (int i = 0; i < n - 2; i++) {int x = nums[i];if (i && x == nums[i - 1] || x + nums[n - 2] + nums[n - 1] < 0) continue;if (x + nums[i + 1] + nums[i + 2] > 0) break; int j = i + 1, k = n - 1;while (j < k) {int s = x + nums[j] + nums[k];if (s > 0) k--;else if (s < 0) j++;else {ans.push_back({x, nums[j], nums[k]});while(++j < k && nums[j] == nums[j - 1]);while(--k > j && nums[k] == nums[k + 1]);}}}return ans;}
};