Re: [闲聊] 每日LeetCode

楼主: fxfxxxfxx (爱丽丝)   2022-10-08 14:13:09
这种头尾双指标要证明是对的通常有几种方法
这里目标是要在已排序的 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币吧
作者: Firstshadow (IamCatづミ'_'ミづ)   2022-10-08 14:16:00
我觉得用ptt看这个眼睛好痛==
作者: Ericz7000 (Ericz7000nolan)   2022-10-08 14:19:00
大师
作者: pandix (面包屌)   2022-10-08 14:36:00
大师
作者: Rushia (みけねこ的鼻屎)   2022-10-08 14:41:00
大师

Links booklink

Contact Us: admin [ a t ] ucptt.com