Article directory
- 3Sum Closest the closest sum of three numbers
-
- Problem Description:
- analyze
- the code
-
- two points
- double pointer
- tag
3Sum Closest The sum of the closest three numbers
Description of problem:
You are given an integer array nums of length n and a target value target. Please select three integers from nums so that their sum is closest to target.
Returns the sum of these three numbers.
It is assumed that there is exactly one solution for each set of inputs.
3
< = no u m the s . l e no g t h < = 3000 ? 1000 < = no u m the s [ i ] < = 1000 ? 1 0 4 < = t a r g e t < = 1 0 4 3 <= nums.length <= 3000\ -1000 <= nums[i] <= 1000\ -10^4 <= target<= 10^4 3<=nums.length<=3000?1000<=nums[i]<=1000?104<=target<=104
Analysis
The basic structure is similar to 3Sum, but the data size is reduced.
The violent process is still
o
(
N
3
)
O(N^3)
O(N3).
Still the same as yesterday, sort first, use the structure of double pointers to process, the overall time complexity
o
(
N
2
)
O(N^2)
O(N2).
The yz combination that the double pointer is looking for here requires xyz and the closest target, that is, y + z is the closest
∣
t
a
r
g
e
t
?
x
∣
|target-x|
∣target?x∣.
So after fixing x, fix y, then the double pointer process looks for the yz combination. That is, the double pointer is constantly enumerating the possible yz combinations and recording the xyz results.
For the acceleration of the double pointer part, of course, you can choose not to accelerate, and the data size can also be allowed.
For acceleration, when
x
=
no
u
m
[
i
]
,
the y
=
no
u
m
[
i
+
1
]
,
z
=
no
u
m
[
i
+
2
]
,
the s
u
m
=
x
+
the y
+
z
>
t
a
r
g
e
t
x=num[i],y=num[i+1],z=num[i+2],sum=x+y+z>target
x=num[i], y=num[i + 1], z=num[i + 2], sum=x + y + z>target, at this time a minimum combination larger than target has been found, so There is no need to traverse later.
when
x
=
no
u
m
[
i
]
,
the y
=
no
u
m
[
no
?
2
]
,
z
=
no
u
m
[
no
?
1
]
,
,
the s
u
m
=
x
+
the y
+
z
<
t
a
r
g
e
t
x= num[i],y=num[n-2],z=num[n-1],,sum=x + y + z Of course, binary points can also be used, and the theoretical time complexity is o ( N 2 L o g N ) O(N^2LogN) O(N2LogN),. Time complexity o ( N 2 log ? N ) O(N^2 \log N) O(N2logN) Space Complexity o ( log ? N ) O(\log N) O(logN) Time complexity o ( N 2 ) O(N^2) O(N2) Space Complexity o ( log ? N ) O(\log N) O(logN) The acceleration part, the source of inspiration for ideas
Code
two points
public int threeSumClosest(int[] nums, int target) {<!-- -->
int n = nums.length, ans = 1<<30, diff=1<<30;
if(n==3) return nums[0] + nums[1] + nums[2];
Arrays. sort(nums);
for(int i= 0;i<n-2;i ++ ){<!-- -->
if(i>0 & amp; & amp; nums[i]==nums[i-1]) continue;
int sum = nums[i] + nums[i + 1] + nums[i + 2];
if(sum>=target){<!-- -->
return sum-target<diff?sum:ans;
}
sum = nums[i] + nums[n-1] + nums[n-2];
if(sum<target){<!-- -->
int d = target - sum;
if(d<diff){<!-- -->
ans = sum;
diff = d;
}
continue;
}
for(int j = i + 1;j<n-1;j + + ){<!-- -->
int z = find(nums,j + 1,n-1,target-nums[i]-nums[j]);
sum = nums[i];
sum + = nums[j];
sum + = z;
if(sum==target) return target;
int d = Math.abs(sum-target);
if(d<diff){<!-- -->
ans = sum;
diff = d;
}
}
}
return ans;
}
// find 1st >= target
public int find(int[] arr, int left, int right, int target){<!-- -->
if(arr[left]>target) return arr[left];
if(arr[right]<target) return arr[right];
int mid = 0, l = left, r = right;
while(l<r){<!-- -->
mid = l + (r-l)/2;
if(arr[mid]<target){<!-- -->
l = mid + 1;
}
else{<!-- -->
r = mid;
}
}
if(l>left){<!-- -->
if( Math.abs(arr[l-1] -target)<=Math.abs(arr[l] -target) ){<!-- -->
return arr[l-1];
}
}
return arr[l];
}
Double pointer
public int threeSumClosest(int[] nums, int target) {<!-- -->
int n = nums.length, ans = 1<<30, diff=1<<30;
if(n==3) return nums[0] + nums[1] + nums[2];
Arrays. sort(nums);
for(int i=0; i<n-2; i ++ ){<!-- -->
if(i>0 & amp; & amp; nums[i]==nums[i-1]) continue;
int j=i + 1,k=n-1;
//accelerate
int sum = nums[i] + nums[i + 1] + nums[i + 2];
if(sum>=target){<!-- -->
return sum-target<diff?sum:ans;
}
sum = nums[i] + nums[n-1] + nums[n-2];
//accelerate
if(sum<target){<!-- -->
int d = target - sum;
if(d<diff){<!-- -->
ans = sum;
diff = d;
}
continue;
}
while(j<k){<!-- -->
sum = nums[i] + nums[j] + nums[k];
int d = Math.abs(sum - target);
if(d<diff){<!-- -->
diff = d;
ans = sum;
}
if(sum==target){<!-- -->
return target;
}
else if(sum>target){<!-- -->
k--;
while(j<k & amp; & amp; nums[k]==nums[k + 1]){<!-- -->
k--;
}
}
else{<!-- -->
j + + ;
while(j<k & amp; & amp; nums[j-1]==nums[j]){<!-- -->
j + + ;
}
}
}
}
return ans;
}
Tag
ArrayTwo PointersSort