No.016：3Sum Closest-白红宇的个人博客

No.016：3Sum Closest

发布日期：2021-05-09 03:58:58 浏览次数：17 分类：博客文章

本文共 2598 字，大约阅读时间需要 8 分钟。

问题：

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).

官方难度：

Medium

翻译：

给定一个长度为n的无序数组S，找出其中的3个整数，使这3个整数的和最接近于一个给定的目标值，返回这3个整数的和。

假定整个数组中的解是唯一的。

例子：

数组S:{ -1,2,1,-4}，目标值target=1。

解为2（-1+2+1=2）。

这题的解法，与No.015（3Sum）的解法基本相同，先排序，然后通过外循环遍历+内循环夹逼的方法实现。

与3Sum问题不同的是，除了维护上一个值是否与当前值相同，其余的优化方法都不能使用。另外，previous的初始值，不能影响第一次计算。

维护一个差值closest，这个值要保证是正数。由于解唯一确定，所以在循环过程中，如果出现closest=0的情况，可以直接返回。注意返回值不是差值，而是三个数值的和。

注意入参检查。

解题代码：

1 // 返回值是数组3个元素的和，不是差值 2     public static int threeSumClosest(int[] nums, int target) { 3         if (nums == null || nums.length < 3) { 4             throw new IllegalArgumentException("Input error"); 5         } 6         Arrays.sort(nums); 7         // 初始差值和返回值 8         int returnNo = Integer.MAX_VALUE; 9         int closest = Integer.MAX_VALUE;10         int previous = Integer.MAX_VALUE;11         for (int i = 0; i < nums.length - 2; i++) {12             if (nums[i] == previous) {13                 continue;14             }else{15                 previous = nums[i];16             }17             // 数组剩余部分夹逼18             int left = i + 1;19             int right = nums.length - 1;20             // 转化为2Sum Closest问题21             int remainTarget = target - nums[i];22             int sum;23             int preLeft = Integer.MIN_VALUE, preRight = Integer.MIN_VALUE;24             while (left < right) {25                 if (nums[left] == preLeft) {26                     left++;27                     continue;28                 }29                 if (nums[right] == preRight) {30                     right--;31                     continue;32                 }33                 sum = nums[left] + nums[right];34                 // 解唯一确定，直接返回35                 if (remainTarget - sum == 0) {36                     return sum + nums[i];37                 }38                 // 最小值替换，返回值赋值39                 int temp = Math.abs(remainTarget - sum);40                 if (temp < closest) {41                     returnNo = nums[i] + nums[left] + nums[right];42                     closest = temp;43                 }44                 if (remainTarget - sum > 0) {45                     left++;46                 } else {47                     right--;48                 }49             }50         }51         return returnNo;52     }

threeSumClosest

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章