首页 > 代码库 > 【leetcode刷题笔记】3Sum Closest

【leetcode刷题笔记】3Sum Closest

2024-07-13 20:03:01   219人阅读

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

题解：3Sum类似，只要维护一个变量closest作为当前和target最近的和。如果之间能够凑出来target，返回target就可以了。

有一个坑就是closest初始化的时候不能初始化为Integer.MAXVALUE，否则closest-target当target<0的时候会溢出。

比如输入 [-3,-2,-5,3,-4], -1 Integer.MAXVALUE-(-1)瞬间就溢出了。

代码如下：

 1 public class Solution { 2     public int threeSumClosest(int[] num, int target) { 3         if(num == null || num.length == 0) 4             return 0; 5         Arrays.sort(num); 6         int closest = Integer.MAX_VALUE/2; 7          8         for(int i = 0;i < num.length;i++){ 9             int start = i + 1;10             int last = num.length-1;11             while(start < last){12                 int sum = num[i] + num[start] + num[last];13                 if(sum == target)14                     return sum;15                 else if(sum < target)16                 {17                     start++;18                 }19                 else{20                     last--;21                 }22                 closest = Math.abs(closest-target) > Math.abs(sum - target)?sum:closest;23             }24         }25         26         return closest;27     }28 }


联系
我们