18. 4Sum

1. 问题描述

Given an array S of n integers, are there elements a, b, c, and d in S 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.

For example, given array S = [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]
]

Tags：Array Hash Table Two Pointers

Similar Problems： (E) Two Sum (M) 3Sum

2. 解答思路

3. 代码

 1 #include <vector>
 2 #include <map>
 3 #include <algorithm>
 4 #include <string>
 5 using namespace std;
 6 class Solution {
 7 public:
 8     vector<vector<int>> fourSum(vector<int>& nums, int target) {
 9         vector<vector<int>> vResult;
10         if (!Validate(nums))
11         {
12             return vResult;
13         }
14         std::map<std::string, bool> isExist;//用于存储已存在的四元组
15         int vSize = nums.size();
16         std::sort(nums.begin(), nums.end());
17         int Fir, Sec, Trd, Fou;
18         for (Fir=0; Fir<=vSize-4; Fir++)
19         {
20             int t1 = target - nums[Fir];
21             for (Sec=Fir+1; Sec<=vSize-3; Sec++)
22             {
23                 int t = t1 - nums[Sec];
24                 for (Trd=Sec+1, Fou=vSize-1; Trd<Fou;)
25                 {
26                     int sum = nums[Trd] + nums[Fou];
27                     if (sum < t)
28                     {
29                         Trd++;
30                     }
31                     else if (sum > t)
32                     {
33                         Fou--;
34                     }
35                     else
36                     {
37                         std::vector<int> vTemp;
38                         vTemp.push_back(nums[Fir]);
39                         vTemp.push_back(nums[Sec]);
40                         vTemp.push_back(nums[Trd]);
41                         vTemp.push_back(nums[Fou]);
42                         
43                         char pBuf[100];
44                         sprintf(pBuf, "%d_%d_%d_%d", nums[Fir], nums[Sec], nums[Trd], nums[Fou]);
45                         std::string str(pBuf);                        
46                         if (0 == isExist.count(str))
47                         {
48                             isExist.insert(std::make_pair(str, true));
49                             vResult.push_back(vTemp);
50                         }
51                         
52                         Trd++;
53                     }
54                 }
55             }
56         }
57         return vResult;
58     }
59 private:
60     bool Validate(vector<int>& nums)
61     {
62         if (nums.size() < 4)
63         {
64             return false;
65         }
66         return true;
67     }
68 };

18. 4Sum

1. 问题描述

2. 解答思路

3. 代码

4. 反思