[LintCode/LeetCode] 3Sum Closest

ShevaKuilin 发布于2019-08-14 15:42 / 477人阅读

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

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 2019-08-14 15:42 评论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
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
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
[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