19.1.29 [LeetCode 18] 4Sum

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

The solution set must not contain duplicate quadruplets.

Example:

Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

 1 class Solution {
 2 public:
 3     vector<vector<int>> fourSum(vector<int>& nums, int target) {
 4         int size = nums.size();
 5         sort(nums.begin(), nums.end());
 6         vector<vector<int>> ans;
 7         for (int i = 0; i < size; i++) {
 8             if (i > 0 && nums[i] == nums[i - 1])continue;
 9             for (int j = i + 1; j < size - 2; j++) {
10                 if (j > i + 1 && nums[j] == nums[j - 1])continue;
11                 int p = j + 1, q = size - 1;
12                 int res = target - nums[i] - nums[j];
13                 while (p < q) {
14                     int tmp = nums[p] + nums[q];
15                     if (tmp < res)p++;
16                     else if (tmp == res) {
17                         vector<int> tt;
18                         tt.push_back(nums[i]);
19                         tt.push_back(nums[j]);
20                         tt.push_back(nums[p]);
21                         tt.push_back(nums[q]);
22                         ans.push_back(tt);
23                         while (nums[p + 1] == nums[p])p++;
24                         while (nums[q - 1] == nums[q])q--;
25                         p++, q--;
26                     }
27                     else q--;
28                 }
29             }
30         }
31         return ans;
32     }
33 };

View Code

跟3sum基本相同

注定失败的战争，也要拼尽全力去打赢它；就算输，也要输得足够漂亮。