4Sum

Given an array S of n integers, are there elements abc, 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:

  • Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ? b ? c ? d)
  • 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)
C++:
01 bool compare(int i, int j)
02 {
03     return i<j;
04 }
05 class Solution {
06 public:
07     vector<vector<int> > fourSum(vector<int> &num, int target) {
08         // Start typing your C/C++ solution below
09         // DO NOT write int main() function
10         sort(num.begin(),num.end(),compare);
11         vector<vector<int>> result;
12         int n=num.size();
13         if(n<3) return result;
14         for(int i=0i<n3; )
15         {
16             for(int j=i+1j<n2;  )
17             {
18                 int p=j+1;
19                 int q=n1;
20                 while(p<q)
21                 {
22                     int t=num[i]+num[j]+num[p]+num[q]target;
23                     if(t==0)
24                     {
25                         vector<int> item;
26                         item.push_back(num[i]);
27                         item.push_back(num[j]);
28                         item.push_back(num[p]);
29                         item.push_back(num[q]);
30                         result.push_back(item);
31                         p++;
32                         while((p<q)&&(num[p]==num[p1]))    p++;
33                     }
34                     else if(t<0)
35                     {
36                         p++;
37                     }
38                     else
39                     {
40                         q;
41                     }
42                 }
43                 j++;
44                 while((j<n2)&&(num[j]==num[j1]))  j++;
45             }
46             i++;
47             while((i<n3)&&(num[i]==num[i1])) i++;
48         }
49     }
50 };
Advertisements
This entry was posted in Array and linked list. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s