4Sum

My intuition is derive the solution from 3Sum. Basically, the same idea.

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

15. 3Sum

The idea is to sort the array first and scan the array from left to right. When scanning the array, we fix the current element and start check its right subarray by two pointers. Since the array is sorted, for the two pointers, we know that:
1. Sum of nums[i], nums[l], nums[r] is less than target, move the left pointer.
2. Sum of nums[i], nums[l], nums[r] is larger than target, move the right pointer.
3. Target is found, save the triple elements.

Since the problem requires the result to exclude dups, I first tried to use set to store the triples but got TLE. Then I have to add line 8, 13-14 to achieve the requirement.

1:  class Solution {  
2:  public:  
3:    vector<vector<int>> threeSum(vector<int>& nums) {  
4:      vector<vector<int>> res;  
5:      if (nums.size() < 3) return res;  
6:      sort(nums.begin(), nums.end());  
7:      for (int i = 0; i < nums.size()-2; i++) {  
8:        if (i == 0 || nums[i-1] != nums[i]) {  
9:          int l = i+1, r = nums.size()-1, t = -nums[i];  
10:          while (l < r) {  
11:            if (nums[l]+nums[r]==t) {  
12:              res.push_back(vector<int>{nums[i],nums[l],nums[r]});   
13:              while ((l < r) && (nums[l] == nums[l+1])) l++;  
14:              while ((l < r) && (nums[r] == nums[r-1])) r--;  
15:              l++, r--;  
16:            }  
17:            else if (nums[l]+nums[r]<t) l++;  
18:            else r--;  
19:          }  
20:        }  
21:      }  
22:      return res;  
23:    }  
24:  };