Re: [閒聊] 每日LeetCode

作者: pandix (麵包屌)   2022-10-08 13:02:09
※ 引述《Rushia (みけねこ的鼻屎)》之銘言:
: 16. 3Sum Closest
: 給定一個長度大於3的整數陣列和一個數字target,求出最接近target的任意三數之和,
: 假定測資只存在恰好一解。
: Example 1:
: Input: nums = [-1,2,1,-4], target = 1
: Output: 2
: Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
: 法二 雙指標
: 思路:
: 1.題目要求與target最接近的sum,所以:
: A + B + C = sum ==> 趨近於target
: 我們可以把他移項:
: B + C = 趨近於target - A
: 該問題就會退化為在陣列裡搜尋最接近 target 的 B + C
: 2.先把整個陣列排序,這樣可以快速的取值且排除掉使用過的組合。
: 3.遍歷陣列,把nums[i]當作第一個加數A,並從右取最大和最小值當B和C。
: sum = A + B + C
: 4.依據狀況移動指標,分兩case:
: 若sum > target 表示我們要再拿更小 right
作者: Rushia (みけねこ的鼻屎)   2022-10-08 13:09:00
應該說如果存在更小的絕對值就會逼近不存在還是會乖乖的遍歷跑完 因為沒提早跳出主要是把n^2壓成n
作者: pandix (麵包屌)   2022-10-08 13:23:00
對 只是說單用絕對值沒辦法解釋正確性

Links booklink

Contact Us: admin [ a t ] ucptt.com