摘要:題目詳情給定一個(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, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.想法給定一個(gè)整數(shù)數(shù)組,我們需要找出數(shù)組中三個(gè)元素的加和,使這個(gè)加和最接近于輸入的target數(shù)值。返回這個(gè)最接近的加和。題目假設(shè)一道題只有一個(gè)答案。
For example,輸入數(shù)組S = {-1 2 1 -4},目標(biāo)和target = 1.
最接近target的加和是 2. (-1 + 2 + 1 = 2).
這道題和第15題很像,所以這道題也可以選擇預(yù)排序算法。
我們先對數(shù)組進(jìn)行預(yù)排序。
然后通過減治思想,我們先鎖定第一個(gè)元素,之后找兩個(gè)元素的加和盡可能接近target和第一個(gè)元素值的差值。
找后兩個(gè)元素的時(shí)候,使用左右指針從兩端查找。
解法public int threeSumClosest(int[] nums, int target) { int min = Integer.MAX_VALUE; Arrays.sort(nums); for(int i=0;iMath.abs(diff)){ min = diff; } if(diff > 0)high--; else low++; } } return target+min; }
文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/70980.html
摘要:返回這三個(gè)值的和。思路一三指針這里的思路和是一樣的,就是用三個(gè)指針獲得三個(gè)值并計(jì)算他們的和。 題外話 鑒于這一題的核心思路和leetcode15的思路相同,可以先寫一下15題并參考一下我之前的一篇博客 題目要求 Given an array S of n integers, find three integers in S such that the sum is closest to...
摘要:這個(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 intege...
摘要:為了避免得到重復(fù)結(jié)果,我們不僅要跳過重復(fù)元素,而且要保證找的范圍要是在我們最先選定的那個(gè)數(shù)之后的。而計(jì)算則同樣是先選一個(gè)數(shù),然后再剩下的數(shù)中計(jì)算。 2Sum 在分析多數(shù)和之前,請先看Two Sum的詳解 3Sum 請參閱:https://yanjia.me/zh/2019/01/... 雙指針法 復(fù)雜度 時(shí)間 O(N^2) 空間 O(1) 思路 3Sum其實(shí)可以轉(zhuǎn)化成一個(gè)2Sum的題,...
摘要:前言從開始寫相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時(shí)也沒有按順序?qū)懍F(xiàn)在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個(gè)索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新 前言 從開始寫leetcode相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時(shí)也沒有按順序?qū)憽F(xiàn)在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個(gè)索引嘻嘻。 順序整理 1~50 1...
摘要:找符合條件的總數(shù)。雙指針區(qū)間考慮邊界,長度,為空,等。之后的范圍用雙指針和表示。若三個(gè)指針的數(shù)字之和為,加入結(jié)果數(shù)組。不要求,所以不用判斷了。同理,頭部兩個(gè)指針向后推移,后面建立左右指針夾逼,找到四指針和為目標(biāo)值的元素。 Two Sum Problem Given an array of integers, find two numbers such that they add up ...
閱讀 854·2023-04-26 00:11
閱讀 2655·2021-11-04 16:13
閱讀 2101·2021-09-09 09:33
閱讀 1472·2021-08-20 09:35
閱讀 3818·2021-08-09 13:42
閱讀 3605·2019-08-30 15:55
閱讀 1040·2019-08-30 15:55
閱讀 2218·2019-08-30 13:55