leetcode16 3Sum Closest

Blackjun 发布于2019-08-14 18:07 / 2178人阅读

摘要：返回这三个值的和。思路一三指针这里的思路和是一样的，就是用三个指针获得三个值并计算他们的和。

题外话

鉴于这一题的核心思路和leetcode15的思路相同，可以先写一下15题并参考一下我之前的一篇博客

题目要求

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的元素的整数数组S，从S中找到三个值，这三个值的距离输入的目标值最近。返回这三个值的和。

思路一：三指针

这里的思路和leetcode15是一样的，就是用三个指针获得三个值并计算他们的和。不同的是和当前的最小距离比较，代码如下

public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int length = nums.length;
        int closest = nums[0]+nums[1]+nums[2] - target;
        for(int i = 0 ; i0){
                    while(nums[k--] == nums[k] && j < k);
                }
                if(value==0){
                    return target;
                }
                if(Math.abs(value) < Math.abs(closest)){
                    closest = value;
                }        
            }
            while(nums[i] == nums[++i] && i < nums.length - 2);
        }
            
        return closest + target;
    }

思路二：hashmap等

同leetcode15，请直接参考我的博客

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

服务器托管 idc机房托管 closest() closest closest()函数 Leetcod

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/67013.html

leetcode 16 3Sum Closest

摘要：题目详情给定一个整数数组，我们需要找出数组中三个元素的加和，使这个加和最接近于输入的数值。返回这个最接近的加和。找后两个元素的时候，使用左右指针从两端查找。题目详情 Given an array S of n integers, find three integers in S such that the sum is closest to a given number, targe...

atinosun 2019-08-16 11:03 评论0 收藏0
[LintCode/LeetCode] 3Sum Closest

摘要：这个题和的做法基本一样，只要在循环内计算和最接近的和，并赋值更新返回值即可。 Problem 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 intege...

ShevaKuilin 2019-08-14 15:42 评论0 收藏0
[Leetcode] 3Sum 4Sum 3Sum Closet 多数和

摘要：为了避免得到重复结果，我们不仅要跳过重复元素，而且要保证找的范围要是在我们最先选定的那个数之后的。而计算则同样是先选一个数，然后再剩下的数中计算。 2Sum 在分析多数和之前，请先看Two Sum的详解 3Sum 请参阅：https://yanjia.me/zh/2019/01/... 双指针法复杂度时间 O(N^2) 空间 O(1) 思路 3Sum其实可以转化成一个2Sum的题，...

trigkit4 2019-08-14 12:29 评论0 收藏0
leetcode 部分解答索引（持续更新～）

摘要：前言从开始写相关的博客到现在也蛮多篇了。而且当时也没有按顺序写现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言从开始写leetcode相关的博客到现在也蛮多篇了。而且当时也没有按顺序写～现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理 1~50 1...

leo108 2019-08-15 14:26 评论0 收藏0
【LC总结】K Sum (Two Sum I II/3Sum/4Sum/3Sum Closest)

摘要：找符合条件的总数。双指针区间考虑边界，长度，为空，等。之后的范围用双指针和表示。若三个指针的数字之和为，加入结果数组。不要求，所以不用判断了。同理，头部两个指针向后推移，后面建立左右指针夹逼，找到四指针和为目标值的元素。 Two Sum Problem Given an array of integers, find two numbers such that they add up ...

awesome23 2019-08-14 15:50 评论0 收藏0