ThreeSumClosest [source code]
public class ThreeSumClosest {
static
/******************************************************************************/
class Solution {
public int threeSumClosest(int[] nums, int target) {
assert nums.length >= 3;
if (nums.length == 3)
return nums[0] + nums[1] + nums[2];
Arrays.sort (nums);
int N = nums.length;
if (target <= nums[0] + nums[1] + nums[2])
return nums[0] + nums[1] + nums[2];
if (target >= nums[N - 1] + nums[N - 2] + nums[N - 3]);
int res = nums[0] + nums[1] + nums[2], min = Math.abs (res - target);
for (int i = 0; i < N - 2; i++) {
int j = i + 1, k = N - 1;
while (j < k) {
int sum = nums[i] + nums[j] + nums[k];
if (Math.abs (sum - target) < Math.abs (res - target)) {
min = Math.abs (sum - target);
res = sum;
}
// (sum > target) ? k-- : j++; // illegal in java
if (sum > target)
k--;
else
j++;
}
}
return res;
}
}
/******************************************************************************/
public static void main(String[] args) {
ThreeSumClosest.Solution tester = new ThreeSumClosest.Solution();
}
}
拿到手也是没什么思路, 稍微笔算了一下也是没看到什么特别好的突破口; 转化为已有问题? 3sum? 怎么转化? 从target开始进行一个逐步搜索? 但是这个复杂度明显会超, 只要故意把target搞的远一点就行了;
tag既然提示了用2pointer, 是不是可以先sort一下? 反正这题是不太可能找到优于N^2的解法的, 所以sort一下没有什么害处;
或者类比已有问题? 之前解3sum的时候, 是降维到2sum处理, 这里是不是也可以用这个降维的思路来做? 如果能够找到一个O(N)的2sum closest, 好像还行?
想了15分钟没思路, 懒得想了;
最后是看discussion之后模仿了一个, 速度是28ms (17%);
三角形枚举
另外, 这题还是有一个枚举三个index的操作, 这个反正是老生常谈了, 不过还是提醒一下, 用三角形思路, 也就是说, 你j和k的起点应该是i + 1, 而不是重新从0开始; 这个应该是一个很本能的操作了; 当然, 有些题目可能是需要从0重新开始的, 不过这个题目这里要做的纯粹就是enumerate all triplets, 那么这个类似排列组合性质的枚举, 是没有必要重复从头开始的;
没有editorial;
discussion最优解:
@vaibhavatul47 said in A n^2 Solution, Can we do better ?:
Here is a solution in Order(N^2). I got help from this post on
[stackoverflow][1]
Can we improve this time complexity ?
int threeSumClosest(vector<int> &num, int target) {
vector<int> v(num.begin(), num.end()); // I didn't wanted to disturb original array.
int n = 0;
int ans = 0;
int sum;
sort(v.begin(), v.end());
// If less then 3 elements then return their sum
while (v.size() <= 3) {
return accumulate(v.begin(), v.end(), 0);
}
n = v.size();
// v[0] v[1] v[2] ... v[i] .... v[j] ... v[k] ... v[n-2] v[n-1]
// v[i] <= v[j] <= v[k] always, because we sorted our array.
// Now, for each number, v[i] : we look for pairs v[j] & v[k] such that
// absolute value of (target - (v[i] + v[j] + v[k]) is minimised.
// if the sum of the triplet is greater then the target it implies
// we need to reduce our sum, so we do K = K - 1, that is we reduce
// our sum by taking a smaller number.
// Simillarly if sum of the triplet is less then the target then we
// increase out sum by taking a larger number, i.e. J = J + 1.
ans = v[0] + v[1] + v[2];
for (int i = 0; i < n-2; i++) {
int j = i + 1;
int k = n - 1;
while (j < k) {
sum = v[i] + v[j] + v[k];
if (abs(target - ans) > abs(target - sum)) {
ans = sum;
if (ans == target) return ans;
}
(sum > target) ? k-- : j++;
}
}
return ans;
}
Edit:Thanks @thr for pointing out that. I have corrected it and also renamed 'mx' by 'ans'.
这个解法总体应该还是不错的; 应该说我就是少走了一步; sort我其实也想到了, 然后类比3sum, 把这个问题降维到2sum我也想到了; 但是我脑子里只有一个O(N)的2sum解法; 事实上, NlgN的2sum解法在解决3sum类问题的时候, 出镜率反而很高; 这个好像之前算3sum的时候总结过一次: 2pointer的做法在2sum的时候不显得有优势, 但是因为当上升到order 3以后, 你几乎可以肯定最好也只能做到N^2, 所以Why not就直接先sort一下降低难度?
将这两个观点一起合并起来: 我们先一个NlgN的sort, 然后一个N个2sum closest, 最后就得到了一个要的结果, 而且复杂度控制在N^2;
另外注意这里ans的初始化问题, 随便取一个极值是不行的;
有人证明不存在比N^2更好的解法:
@hebele said in A n^2 Solution, Can we do better ?:
No there isn't. Proof by contradiction:
If we had subquadratic solution to this problem then we could solve all instances of [3SUM][1] problem with the same complexity (subquadratic). but lower bound of 3SUM problem is O(n^2)
但是事实上, 3sum是已经出现了subquadratic解法的了; 不过小问题, 不管了;
类似的:
@chase1991 said in Java solution with O(n2) for reference:
Similar to 3 Sum problem, use 3 pointers to point current element, next element and the last element. If the sum is less than target, it means we have to add a larger element so next element move to the next. If the sum is greater, it means we have to add a smaller element so last element move to the second last element. Keep doing this until the end. Each time compare the difference between sum and target, if it is less than minimum difference so far, then replace result with it, otherwise keep iterating.
public class Solution {
public int threeSumClosest(int[] num, int target) {
int result = num[0] + num[1] + num[num.length - 1];
Arrays.sort(num);
for (int i = 0; i < num.length - 2; i++) {
int start = i + 1, end = num.length - 1;
while (start < end) {
int sum = num[i] + num[start] + num[end];
if (sum > target) {
end--;
} else {
start++;
}
if (Math.abs(sum - target) < Math.abs(result - target)) {
result = sum;
}
}
}
return result;
}
}
一个小优化:
@mol1203 said in Java solution with O(n2) for reference:
You answer is great. However, we could improve performance a bit by skipping duplicate elements.
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int sum = nums[0] + nums[1] + nums[nums.length - 1];
int closestSum = sum;
for(int i = 0; i < nums.length - 2; i++){
if(i==0 || nums[i]!=nums[i-1]){
int left = i + 1, right = nums.length - 1;
while(left < right){
sum = nums[left] + nums[right] + nums[i];
if(sum < target){
//move closer to target sum.
while(left<right && nums[left] == nums[left+1]){
left++;
}
left++;
}else if(sum > target){
//move closer to target sum.
while(left<right && nums[right] == nums[right-1]){
right--;
}
right--;
}else{
return sum;
}
//update the closest sum if needed.
if(Math.abs(target - sum) < Math.abs(target - closestSum)){
closestSum = sum;
}
}
}
}
return closestSum;
}
还是一个eager advance的技巧, 别说, 这个技巧虽然有时候你认为只不过是一个trivial的改写, 但是很多时候往往真的能带来速度提升;
另一个:
@lu.tong said in Java solution with O(n2) for reference:
I think it would be better to break early when sum==target.
这个有点意思;
一个加了优化的, 貌似速度快很多:
@lingkaicode said in Sharing my Java Optimized solution 5ms, beats 99.9%:
It is just some optimized work after basic 3Sum structure.
public int threeSumClosest(int[] nums, int target) {
if(nums.length<3) return 0;
Arrays.sort(nums);
int min = Integer.MAX_VALUE;int result =Integer.MAX_VALUE;
for(int i=0;i<nums.length-2;i++)
{
if(3*nums[i]>target)
{
int sum3 = nums[i]+nums[i+1]+nums[i+2];
if(Math.abs(sum3-target)<min) return sum3;
//break; //should break here but seems slower after adding it
}
int left = i+1;
int right = nums.length-1;
int sum = target - nums[i];
if(2*nums[right]<sum) {
int sum2 = nums[i]+nums[right]+nums[right-1];
if(Math.abs(sum2-target)<min){
min = Math.abs(target-sum2);
result = sum2;
}
continue;
}
while(left<right)
{
int temp = nums[i] + nums[left]+nums[right];
if(temp==target) return target;
if(2*nums[left]>sum)
{
int sumsum = nums[i]+nums[left]+nums[left+1];
if(Math.abs(sumsum-target)<min){
min = Math.abs(target-sumsum);
result = sumsum;
}
break;
}
else if(Math.abs(target-temp)<min)
{
min = Math.abs(target-temp);
result = temp;
}
if(temp<target)
left++;
else right --;
}
}
return result;
}
大概的优化思路也是清晰的; 他这个优化并不是非常的极端, 只有在超过并且后面只会继续增大的时候, 才prune;
can you do faster?
这里还是要总结一个东西, 真正面试的时候, 很可能会被闻到这样一个能够faster的问题? 这个时候, 当然最好的是能够想到一个确实更先进的算法; 但是假如你的第一个正确算法是类似这个的这种比较穷搜的算法, 那么很多时候一个更加保守的回答是, 先做pruning; 因为在类似DFS或者穷搜的这种算法当中, pruning的重要性你真的是不要低估;
submission最优解: 12(100):
class Solution {
//one pass solution -- same iteration approach as threeSum problem
public int threeSumClosest(int[] nums, int target) {
int len = nums.length;
Arrays.sort(nums);//dual-pivot quicksort
//loCount and hiCount denote your lowest, and higher values closest to target
int loCount = nums[0] + nums[1] + nums[2], hiCount = nums[len - 3] + nums[len - 2] + nums[len - 1];
//check for easy(edge case) solution
if (loCount >= target)
return loCount;
if (hiCount <= target)
return hiCount;
//iterate through array via incrementing head pointer
for (int head = 0; head < nums.length - 2; head++) {
//lo and hi denotes smallest and biggest values of current head iteration
int lo = nums[head] + nums[head + 1] + nums[head + 2], hi = nums[head] + nums[len - 2] + nums[len - 1];
if (lo > target) {//if lo is too big, update your hiCount and terminate loop
if (hiCount > lo)
hiCount = lo;
break;
} else if (hi < target) { //if hi is too small, update your loCount and skip current iteration
if (loCount < hi)
loCount = hi;
continue;
}
//low and high denotes your array index pointers
int low = head + 1, high = len - 1;
while (low < high) {
int sum = nums[low] + nums[high] + nums[head];
if (sum == target) {
return target;
} else if (sum < target) {
if (loCount < sum)
loCount = sum;
while (++low < len - 1 && nums[low] == nums[low - 1])
;
} else {
if (hiCount > sum)
hiCount = sum;
while (--high > head + 1 && nums[high] == nums[high + 1])
;
}
}
}
return (hiCount - target) > (target - loCount) ? loCount : hiCount;
}
}
大概看了一下, 这个算法之所以能这么快, 主要原因还是有优化, 但是他的这些pruning并不是那么trivial; 应该说, 这个算法把我在discussion看到的几乎所有的优化pruning都加上了: 长度等于3的Corner Case, 然后target过大过小的, 然后eager advance, 还有premature exit on hit.
当然, 这个算法更优意思的一点, 是怎么通过维护两个Count变量来完成一个pruning的. 这个pruning就比上面刚看到的那个pruning更加的有意思和优雅; 具体的可以看看他的代码, 对于loCount和hiCount的维护很细腻;
Problem Description
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).
Difficulty:Medium
Total Accepted:160.3K
Total Submissions:508.3K
Contributor:LeetCode
Companies
bloomberg
Related Topics
arraytwo pointers
Similar Questions
3Sum3Sum Smaller