Re: [閒聊] 每日LeetCode
這種頭尾雙指標要證明是對的通常有幾種方法
這裡目標是要在已排序的 nums 中找 left, right
使得 nums[left] + nums[right] 越接近 target 越好
第一種：循環不變量/遞迴
假如 nums[left] + nums[right] < target
（大於的情況是對稱的可以依樣畫葫蘆）
因為 nums[right] 是目前最大值（因為排序）
所以對於所有 left < j < right，我們有
nums[left] + nums[j] < nums[left] + nums[right] < target
也就是用 left 配其他不是 right 的人都只會離 target 更遠
因此那些包含 left 的候選人，就已經全部檢查過了
假設 A_{left,right} 代表考慮 nums[left], ..., nums[right] 中
最接近 target 的距離 dis
在每個迴圈開始時，我們就都有
A_{0,n-1} = min(dis, A{left,right})
之後不管更新 left 還 right，這個等式都不會變
（因為移動就代表那個值的可能性已經全部被考慮過了）
迴圈出來時 dis 就是 A_{0,n-1}，也就是最小的距離
(當然這題要回答讓距離最小的那個總和)
還有第二種證法是我比較喜歡的
假設讓距離最小的 index 分別是 a, b 且 a < b
(也就是 nums[a] + nums[b] 距離 target 最近)
因為 left 和 right 不斷向內縮
總有一天要麼 left 先碰到 a，要麼 right 先碰到 b
假設 left 先變成 a 好了，此時 right 還大於 b
因為 a, b 是最佳解，且 nums[right] > nums[b] （因為排序）
所以 nums[a] + nums[right] - target 不可能是負的，否則就有
num[a] + nums[b] - target < nums[a] + nums[right] - target < 0
這樣 a, b 就不是最佳解就會矛盾
因此我們的演算法此時一定會移動 right
而且會一直持續到 right 變成 b 為止
因此這個演算法一定會經過最佳解並把答案更新
第11題的 Container With Most Water 也可以用類似方法證
打這麼多廢話應該有不少p幣吧
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.16.175 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1665209591.A.7F0.html
→
10/08 14:16,
1年前
, 1F
10/08 14:16, 1F
→
10/08 14:19,
1年前
, 2F
10/08 14:19, 2F
推
10/08 14:36,
1年前
, 3F
10/08 14:36, 3F
推
10/08 14:41,
1年前
, 4F
10/08 14:41, 4F
討論串 (同標題文章)
完整討論串 (本文為第 38 之 719 篇)：
閒聊
1
3