资讯专栏INFORMATION COLUMN

[LintCode/LeetCode] 3Sum Closest

ShevaKuilin / 470人阅读

摘要:这个题和的做法基本一样,只要在循环内计算和最接近的和,并赋值更新返回值即可。

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

Notice

You may assume that each input would have exactly one solution.

Example

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

Challenge

O(n^2) time, O(1) extra space

Note

这个题和3Sum的做法基本一样,只要在循环内计算和target最接近的和sum,并赋值更新返回值min即可。

Solution
public class Solution {
    public int threeSumClosest(int[] A ,int target) {
        int min = Integer.MAX_VALUE - target;
        if (A.length < 3) return -1;
        Arrays.sort(A);
        for (int i = 0; i <= A.length-3; i++) {
            int left = i+1, right = A.length-1;
            while (left < right) {
                int sum = A[i]+A[left]+A[right];
                if (sum == target) return sum;
                else if (sum < target) left++;
                else right--;
                min = Math.abs(min-target) < Math.abs(sum-target) ? min : sum;
            }
        }
        return min;
    }
}

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

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

相关文章

  • [LintCode/LeetCode] 3Sum

    摘要:双指针法的解法。然后用和夹逼找到使三数和为零的三数数列,放入结果数组。对于这三个数,如果循环的下一个数值和当前数值相等,就跳过以避免中有相同的解。 Problem Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplet...

    Sunxb 评论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 评论0 收藏0
  • 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 评论0 收藏0
  • 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 评论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 评论0 收藏0

发表评论

0条评论

ShevaKuilin

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<