leetcode 16 3Sum Closest

atinosun 发布于2019-08-16 11:03 / 1880人阅读

摘要：题目详情给定一个整数数组，我们需要找出数组中三个元素的加和，使这个加和最接近于输入的数值。返回这个最接近的加和。找后两个元素的时候，使用左右指针从两端查找。

题目详情

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.

给定一个整数数组，我们需要找出数组中三个元素的加和，使这个加和最接近于输入的target数值。返回这个最接近的加和。题目假设一道题只有一个答案。

For example,输入数组S = {-1 2 1 -4},目标和target = 1.
最接近target的加和是 2. (-1 + 2 + 1 = 2).

想法

这道题和第15题很像，所以这道题也可以选择预排序算法。

我们先对数组进行预排序。

然后通过减治思想，我们先锁定第一个元素，之后找两个元素的加和尽可能接近target和第一个元素值的差值。

找后两个元素的时候，使用左右指针从两端查找。

解法

   public int threeSumClosest(int[] nums, int target) {
        int min = Integer.MAX_VALUE;
        Arrays.sort(nums);
        
        for(int i=0;i Math.abs(diff)){
                    min = diff;
                    }
                if(diff > 0)high--;
                else low++;
                    
            }
        }
        
        return target+min;
    }

私有云混合云 closest() closest closest()函数 Leetcod

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

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

leetcode16 3Sum Closest

摘要：返回这三个值的和。思路一三指针这里的思路和是一样的，就是用三个指针获得三个值并计算他们的和。题外话鉴于这一题的核心思路和leetcode15的思路相同，可以先写一下15题并参考一下我之前的一篇博客题目要求 Given an array S of n integers, find three integers in S such that the sum is closest to...

Blackjun 2019-08-14 18:07 评论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