| 4 | class Solution { |
| 5 | public: |
| 6 | vector<vector<int>> fourSum(vector<int>& nums, int target) { |
| 7 | vector<vector<int>> result; |
| 8 | int n = (int)nums.size(); |
| 9 | sort(nums.begin(), nums.end()); |
| 10 | for (int i = 0; i < n; ++i) { |
| 11 | if (i > 0 && nums[i] == nums[i - 1]) continue; |
| 12 | for (int j = i + 1; j < n; ++j) { |
| 13 | if (j > i + 1 && nums[j] == nums[j - 1]) continue; |
| 14 | long long remaining = (long long)target - nums[i] - nums[j]; |
| 15 | int l = j + 1, r = n - 1; |
| 16 | while (l < r) { |
| 17 | long long two = (long long)nums[l] + nums[r]; |
| 18 | if (two == remaining) { |
| 19 | result.push_back({nums[i], nums[j], nums[l], nums[r]}); |
| 20 | int leftVal = nums[l], rightVal = nums[r]; |
| 21 | while (l < r && nums[l] == leftVal) ++l; |
| 22 | while (l < r && nums[r] == rightVal) --r; |
| 23 | } else if (two < remaining) { |
| 24 | ++l; |
| 25 | } else { |
| 26 | --r; |
| 27 | } |
| 28 | } |
| 29 | } |
| 30 | } |
| 31 | return result; |
| 32 | } |
| 33 | }; |
| 34 | |
| 35 | // Helper main for quick local testing |