LeetCode (13): 3Sum Closest

时间:2023-03-08 16:39:03

https://leetcode.com/problems/3sum-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).

【中文描述】

给定一个数组n个数字,并且给一个target数,要求从这个数组中找出3个数字,其和最接近这个target。比如上面例子显示的那样。

同时,leetCode很仁慈的说,假定每个数组中只会有一个唯一解。

————————————————————————————————————————————————————————————

【初始思路】

这道题其实和3SUM普通那道题差不多(3SUM下面讨论一下)。  无非就是找最接近target的3元组。那我们完全可以套用3SUM的代码,稍加改动即可。

怎么改?

首先,3SUM的代码其实是把所有3元组全部算出来了。那我们在计算所有3SUM的同时,实时地把最接近的3元组记录下来不就好了。然后在计算结束后,我们返回最接近的这个值不就完了?

此外,low和high的跳跃和3SUM的原则是一样的,如果比target还大,high--,如果比target小,low++.  关于3SUM算法下面会讨论,这种跳跃方法,low和high肯定能计算到所有的数字,不会有漏掉的可能。

【Show me the Code!!!】

 public static int threeSumClosest(int[] nums, int target) {
int len = nums.length;
Arrays.sort(nums); //算出最大可能和 + 最小可能和, 避免最差情况
int max = nums[len - 1] + nums[len - 2] + nums[len - 3];
int min = nums[0] + nums[1] + nums[2];
if(target >= max) return max;
if(target <= min) return min; int diff = Integer.MAX_VALUE;
int result = 0;
for (int i = 0; i < len; i++) {
int low = i + 1;
int high = len - 1;
while (low < high) {
int sum = nums[i] + nums[low] + nums[high];
if(Math.abs(target-sum) < diff) { //只要比diff小,就更新diff,同时记录三元组和
diff = Math.abs(target-sum);
result = sum;
} else {
if(sum > target) high--;
else low++;
}
}
}
return result;
}

3SumClosest

关于3Sum题的反思和分析

https://leetcode.com/problems/3sum/

题目描述:

Given an array S of n integers, are there elements abc in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

  • Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
  • The solution set must not contain duplicate triplets.

For example, given array S = {-1 0 1 2 -1 -4},

    A solution set is:
(-1, 0, 1)
(-1, -1, 2)

中文描述:

给一个数组,要求找出其中的和为0的三个数字的组合。   要求找出所有,并且,所有3元组都必须升序排列,并且不能有重复。看例子就能看懂。

返回类型根据题目要求是: List<List<Integer>> , 一个数字列表的列表。

【思路】

先考虑会不会有特殊情况,自己试了几个例子,发现,如果数组为null或者数组元素个数小于3个的时候,统一返回了空list,这些情况可以单独写代码应对。

接下来就考虑一般情况。

对于数组题,结果不要求返回位置相关信息的。最好都先考虑排序一下,然后再计算,会更简单直观,这个题也不例外。先排序一下:Arrays.sort(nums);

排序后呢?

由于根据题意,要求三元组相加和等于0. 那么,可以肯定的是,需要遍历数组,对于每一个数字nums[i],在余下的数字中找出另外两个数字使其满足加起来=0的条件。

如何在剩余的数组中找到我们想要的两个数字是本题的技巧所在。

最简单的办法是i, j指针2层循环。这是蛮力算法,仔细想想你会发现,其实很多计算都是不必要的。

首先,数组是已经从小到大排序好的,而这两个数之和是个固定值0-nums[i], 我们可不可以在一次遍历里用两个指针,其和等于0-nums[i]是一种情况, 其和不等于0-nums[i]是另外一种情况,之后移动两个指针进行下一次计算不就可以了么?

两个指针遍历一维数组,首先想到的办法就是两边各放一个,然后往中间靠拢。我们来分析一下可不可行。

假设,两个指针:low和high, low指向i+1(因为nums[i]已经确定了,low应该从i的下一位开始遍历), high指向数组最后一个元素。 两者相加,无非3种可能性:(1)大于target(2)小于target(3)等于target。挨个分析一下:

(1)大于target. 由于数组已经排序好了,在nums[low] + nums[high] > target后,由于我们要对两个指针做微调,让它尽可能达到target值。假设我们调low,low+1。那么由于nums[low+1] > nums[low],所以low移动后的nums[low] + nums[high] > target 就是必然的了!事实上,这个值比上面那个值还大!所以这个情况下,应该移动high,让high-1。 那么nums[low] + nums[high]就比上面的值稍小一点,靠近了一点target,然后才有可能和target相等;

(2)小于target. 同理,这个时候应该移动low+1,而不是high-1.

(3)如果nums[low] + nums[high] = target。 那么low和high需要各自向里面移动一位。low++,high--。

这样,就能够保证遍历到所有的可能性。

【重复元素!】

题目没有说没有重复元素,我试了几个例子,确实是,如果有重复元素,官方的结果里是去重的。说明可能会有重复元素的用例。

那怎么办呢?上面的办法,如果不加任何实时去重机制,那结果里肯定会有一大堆重复结果。如果我们在结果里去重,就慢得多了。因为首先重复计算了很多结果,最终又得去掉他们,做了无用功。

那我们就考虑如何在上面的机制里实时去重。

还是回到数组已经排序的特性上来,考虑下面的序列:

-3,  -1, -1, -1, -1, 0,   1,   1,   1,   4,   4,   5

i    low                                                 high

当i指向-3的时候,起初low在-1的位置,而high在5的位置,-1+5 > 3,high回退到4。 -1+4 = 3。这个时候成功了,好我们记录下这组结果。记录结束后呢?如何处理?直接low++,high--?

那么low+1又到了-1,而high-1后到了4(如下面序列), -1+4 =3, 这组结果就肯定被记录下来了。这就出现了重复结果。

    -3,  -1, -1, -1, -1, 0,   1,   1,   1,   4,   4,   5

i          low                                high

考虑排序数组的特性,由于当low在-1的时候已经计算了一个结果了(-3,-1,4),那么下一个low遇到-1的时候,是不是可以直接跳过?显然,跳过后对结果没有任何影响,因为当前值只要不变,我们想找的另外一个值肯定不会变!而对于high,也应该同步跳过4,因为low已经跳过了-1到达了0,4就绝对不可能是合理的结果了(0+4>3)。所以high也需要跳过4。

可以了么?考虑下面的串:

    -3, -3  -1, -1, -1, -1, 0,   1,   1,   1,   4,   4,   5

i        low                                                  high

当i指向第一个-3的时候,我们势必能计算出一些结果来。等low和high在中间相遇的时候,此轮遍历结束,i++。这个时候i又指向了-3,再计算一遍的话,显然会有重复结果。怎么办?

我们在上面推移low和high的同时,其实可以同步推移i,因为 i 的值对循环内部的算法不产生任何影响,我们直接把指向第一个-3的i指向第二个-3。 相当于忽略掉重复的-3。 这样,本轮循环结束后,i++之后,肯定就会到达下一个新值,而不再重复-3. 这个是可行的

最后,我们看看代码

 public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if(nums == null || nums.length < 3) return result;
Arrays.sort(nums);
for(int i = 0; i < nums.length; i++){
int low = i+1;
int high = nums.length -1;
while(low < high){
if(nums[i] + nums[low] + nums[high] == 0){
result.add(Arrays.asList(nums[i], nums[low], nums[high]));
while(i + 1 < nums.length && nums[i + 1] == nums[i]) i++;//去重考虑.
while(low + 1 < nums.length && nums[low] == nums[low + 1]) low++;//因为i移动的话,low肯定要移动.最终low肯定停留在i后一位,所以没问题
while(high - 1 >= 0 && nums[high] == nums[high - 1]) high--;//去重考虑
/**
* 去重结束后,low和high往中间汇合
* 并且,在当前low+high = 0 - nums[i]的情况下,low和high是唯一的组合.所以可以同时推移
*/
low++;
high--;
} else if(nums[i] + nums[low] + nums[high] > 0) {
/**
* 不等情况(1)
*/
high--;
} else low++;//不等情况(2)
}
}
return result;
}

3Sum