LeetCode

LeetCode_4Sum

 1 class Solution {
 2 public:
 3     vector<vector<int> > fourSum(vector<int> &num, int target) {
 4         // Start typing your C/C++ solution below
 5         // DO NOT write int main() function
 6          vector<vector<int> > output; 
 7          if(num.size()<4) return output; 
 8          
 9          int sum;
10          sort(num.begin(), num.end());
11          
12          for(int i =0; i< num.size() -3 ;){
13            for(int j = i+ 1; j < num.size() - 2; ){
14                 int startS = j + 1 ;
15                 int endS = num.size() - 1 ;
16                 
17                 while(startS < endS){
18               
19                     sum = num[i] + num[j] + num[startS] + num[endS];
20                     if(sum == target) {
21                         vector<int> triplet;  
22                         triplet.push_back(num[i]); 
23                         triplet.push_back(num[j]); 
24                         triplet.push_back(num[startS]);  
25                         triplet.push_back(num[endS]);  
26                         output.push_back(triplet);  
27                         startS++ ;
28                         while(num[startS] == num[startS-1] && startS < endS) startS++;
29                     }
30                     if(sum < target)
31                         startS ++;
32                     else
33                             endS --;    
34                 }   
35                 j++ ;
36                 while(num[j] == num[j-1] && j < num.size() -2 ) j++ ;
37              }
38              i++;
39              while(num[i] == num[i-1] && i< num.size() -3) i ++;     
40          }        
41          return output;
42     }
43 };
同前面的3sum 差不多
--------------------------------------------------------------------天道酬勤！