3 Sum Closest

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

For example, given array S = {-1 2 1 -4}, and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

C++:
01 int compare(const void* a, const void* b)
02 {
03     return (*(int*)a-*(int*)b);
04 }
05 
06 int threeSumClosest(vector<int> &num, int target)
07 {
08     int size=num.size();
09     int* A=new int[size];
10     for(int i=0;i<size;i++)
11         A[i]=num[i];
12     qsort(A,size,sizeof(int),compare);
13     int gap=abs(A[0]+A[1]+A[2]target);
14     int sum=A[0]+A[1]+A[2];
15     for(int i=0;i<size2;i++){
16         for(int j=i+1,k=size1;j<k  ; ){
17             int r=A[i]+A[j]+A[k];
18             if(r==target){
19                 return r;
20             }
21             else if(r<target){
22                 int g=targetr;
23                 if(g<gap){
24                     gap=g;
25                     sum=r;
26                 }
27                 j++;
28             }
29             else{
30                 int g=rtarget;
31                 if(g<gap){
32                     gap=g;
33                     sum=r;
34                 }
35                 k;
36             }
37         }
38     }
39     return sum;
40 }
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