No.016 3Sum Closest

16. 3Sum Closest

  • Total Accepted: 86565
  • Total Submissions: 291260
  • Difficulty: Medium

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的解法有点类似,我们可以先将数组排序,然后将数组中的数从左到右依次确定为第一个数,在其右边的数中寻找最接近的target的数即可。重要的是判断逻辑的思路。代码如下:

 1 public int threeSumClosest(int[] nums, int target) {
 2     if (nums == null || nums.length < 3) {
 3         return 0;
 4     }
 5         
 6     Arrays.sort(nums);
 7     
 8     int closest = nums[0]+nums[1]+nums[2] ;
 9     
10     for(int i = 0 ; i < nums.length-2 ; i++){
11         int l = i+1 ;
12         int r = nums.length-1 ;            
13         while(l < r){
14             int sum = nums[i] + nums[l] + nums[r] ;
15             if(sum == target){
16                 return sum ;
17             }else if(sum < target){
18                 /*
19                  * 三种情况:
20                  *     1、closest < sum < target --->closest = sum
21                  *     2、sum < target < closest --->| target-sum < closest-target ---> closest = sum
22                  *                                   | target-sum >= closest-target --> closest不变
23                  *     3、sum <= closest <= target ---> closest不变
24                  */
25                 if(sum > closest){
26                     //情况1
27                     closest = sum ;
28                 }else if(closest > target){
29                     //情况2
30                     if(target-sum < closest-target){
31                         //情况2.1,
32                         closest = sum ;
33                     }
34                     //情况2.2不用变化
35                 }
36                 //情况3不同变化
37                 l++ ;
38             }else{
39                 //分析同上
40                 if(sum < closest){
41                     closest = sum ;
42                 }else if(closest < target){
43                     if(sum-target <= target-closest){
44                         closest = sum ;
45                     }
46                 }
47                 r-- ;
48             }
49         }
50         
51     }        
52     return closest ;
53 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏mathor

LeetCode75.颜色分类

 这道题两种做法,一种是用计数排序,因为告诉了你只有3种数字,所以直接创建一个长度为3的数组arr,然后遍历一遍原数组,每出现一次某个数,arr对应位置的值...

702
来自专栏calmound

uva Andy's First Dictionary

题目很简单,数组开大就好,5000但加上重复就不够了10000都小,sort排序前闭合后开,对二维字符窜排序用结构体,所以只有一组的时候只是本身但是不会出现RE...

3474
来自专栏青青天空树

3032-杨辉三角

还记得中学时候学过的杨辉三角吗?具体的定义这里不再描述,你可以参考以下的图形: 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 ...

1143
来自专栏Golang语言社区

map按key和按value排序

看一个题: 查找和排序 题目:输入任意(用户,成绩)序列,可以获得成绩从高到低或从低到高的排列,相同成绩 都按先录入排列在前的规则处理。 例示: jack 70...

3653
来自专栏前端儿

字符串替换

每行数据是一个字符串,长度不超过1000  数据以EOF结束输出对于输入的每一行,输出替换后的字符串样例输入

2032
来自专栏xiaoxi666的专栏

最长公共子串+最长公共子序列

1、先建立一个二维数组array[str1.size()][str2.size()](全部初始化为0),初始化第一行和第一列(元素相同处置1),然后进入状态方程

1.2K2
来自专栏Golang语言社区

map按key和按value排序

看一个题: 查找和排序 题目:输入任意(用户,成绩)序列,可以获得成绩从高到低或从低到高的排列,相同成绩 都按先录入排列在前的规则处理。 例示: jack 70...

5408
来自专栏一个会写诗的程序员的博客

Sting str = "aaaa" 的形式定义一个字符串最大长度只能有 65534 个。

为什么呢?因为在class文件的规范中, CONSTANT_Utf8_info表中使用一个16位的无符号整数来记录字符串的长度的,最多能表示 65536个字节,...

802
来自专栏chenjx85的技术专栏

leetcode-643-Maximum Average Subarray I

1172
来自专栏机器学习从入门到成神

牛客网刷题汇总(一)附解析

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

7172

扫码关注云+社区

领取腾讯云代金券