[LintCode/LeetCode] 3Sum Closest

ShevaKuilin 發(fā)布于2019-08-14 15:42 / 609人閱讀

摘要：這個(gè)題和的做法基本一樣，只要在循環(huán)內(nèi)計(jì)算和最接近的和，并賦值更新返回值即可。

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

這個(gè)題和3Sum的做法基本一樣，只要在循環(huán)內(nèi)計(jì)算和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;
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/65952.html

相關(guān)文章

[LintCode/LeetCode] 3Sum

摘要：雙指針?lè)ǖ慕夥āＨ缓笥煤蛫A逼找到使三數(shù)和為零的三數(shù)數(shù)列，放入結(jié)果數(shù)組。對(duì)于這三個(gè)數(shù)，如果循環(huán)的下一個(gè)數(shù)值和當(dāng)前數(shù)值相等，就跳過(guò)以避免中有相同的解。 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 評(píng)論0 收藏0
【LC總結(jié)】K Sum (Two Sum I II/3Sum/4Sum/3Sum Closest)

摘要：找符合條件的總數(shù)。雙指針區(qū)間考慮邊界，長(zhǎng)度，為空，等。之后的范圍用雙指針和表示。若三個(gè)指針的數(shù)字之和為，加入結(jié)果數(shù)組。不要求，所以不用判斷了。同理，頭部?jī)蓚€(gè)指針向后推移，后面建立左右指針夾逼，找到四指針和為目標(biāo)值的元素。 Two Sum Problem Given an array of integers, find two numbers such that they add up ...

awesome23 2019-08-14 15:50 評(píng)論0 收藏0
leetcode16 3Sum Closest

摘要：返回這三個(gè)值的和。思路一三指針這里的思路和是一樣的，就是用三個(gè)指針獲得三個(gè)值并計(jì)算他們的和。題外話鑒于這一題的核心思路和leetcode15的思路相同，可以先寫(xiě)一下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 評(píng)論0 收藏0
leetcode 16 3Sum Closest

摘要：題目詳情給定一個(gè)整數(shù)數(shù)組，我們需要找出數(shù)組中三個(gè)元素的加和，使這個(gè)加和最接近于輸入的數(shù)值。返回這個(gè)最接近的加和。找后兩個(gè)元素的時(shí)候，使用左右指針從兩端查找。題目詳情 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 評(píng)論0 收藏0
[Leetcode] 3Sum 4Sum 3Sum Closet 多數(shù)和

摘要：為了避免得到重復(fù)結(jié)果，我們不僅要跳過(guò)重復(fù)元素，而且要保證找的范圍要是在我們最先選定的那個(gè)數(shù)之后的。而計(jì)算則同樣是先選一個(gè)數(shù)，然后再剩下的數(shù)中計(jì)算。 2Sum 在分析多數(shù)和之前，請(qǐng)先看Two Sum的詳解 3Sum 請(qǐng)參閱：https://yanjia.me/zh/2019/01/... 雙指針?lè)?復(fù)雜度時(shí)間 O(N^2) 空間 O(1) 思路 3Sum其實(shí)可以轉(zhuǎn)化成一個(gè)2Sum的題，...

trigkit4 2019-08-14 12:29 評(píng)論0 收藏0