Re: [閒聊] 每日LeetCode
※ 引述《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--
: 若sum < target 表示我們要拿更大 left++
: 這樣每一步都可以產生更小絕對值的解，不用雙層迴圈求所有和。
這裡訂正一下 不一定每一步都能讓絕對值越來越小 但還是可以保證最小絕對值的解
一定會出現在這種方法的 left, right 組合中 原因就是阿薩斯龍語...真的好強...
舉例: [1, 6, 7, 11], target = 13
第一步: (1, 11), sum = 12, diff = 1
第二步: (6, 11), sum = 17, diff = 4
第三步: (6, 7), sum = 13, diff = 0
diff 是有可能會浮動的
: 5.若當前的sum與target的絕對值小於diff則更新diff和res
: 6.返回res
python 用這種方法還是會 TLE 這裡沒辦法再忍了
注意看 這個剪枝太狠了
在 iterate A 的時候就先檢查後面有可能的最大最小值
最大值 = nums[i] + nums[right-1] + nums[right]
最小值 = nums[i] + nums[left] + nums[left+1]
最大值小於 target 或 最小值大於 target
那這個 nums[i] 基本上就不用理他了 直接把 left 拿到最右邊或是 right 拿到最左邊
Python code:
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
nums.sort()
n = len(nums)
res = float('inf')
for i in range(0, n-2):
left, right = i+1, n-1
if nums[i] + nums[left] + nums[left+1] > target:
right = left + 1
elif nums[i] + nums[right-1] + nums[right] < target:
left = right -1
while left < right:
cur = nums[i] + nums[left] + nums[right]
if abs(target - cur) < abs(target - res):
res = cur
if cur == target:
return target
elif cur < target:
left += 1
else:
right -= 1
return res
--
蛤?
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.251.199.166 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1665205332.A.AB4.html
→
10/08 13:09,
1年前
, 1F
10/08 13:09, 1F
→
10/08 13:10,
1年前
, 2F
10/08 13:10, 2F
→
10/08 13:10,
1年前
, 3F
10/08 13:10, 3F
→
10/08 13:23,
1年前
, 4F
10/08 13:23, 4F
討論串 (同標題文章)