双指针 - 四数之和

题目链接

排序+双指针 首先将数组排序，然后枚举其中的两个数，剩下两个数从数组中开头和结尾进行枚举。 复杂度$O(n^3)$

class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { vector<vector<int>> ret; sort(nums.begin(), nums.end()); int n = nums.size(); for (int i = 0; i < n; ++i) { if (i && nums[i] == nums[i-1]) continue; for (int j = i+1; j < n; ++j) { if (j > i+1 && nums[j] == nums[j-1]) continue; int l = j+1; int r = n-1; int num = target-nums[i]-nums[j]; while (l < r) { int sum = nums[l] + nums[r]; if (sum > num) --r; else if (sum < num) ++l; else { if (ret.empty() || ret.back()[0] != nums[i] || ret.back()[1] != nums[j] || ret.back()[2] != nums[l]) { ret.push_back({nums[i], nums[j], nums[l], nums[r]}); } ++l; } } } } return ret; } };