【算法】双指针与滑动窗口三相向双指针——比较、排除、收缩摘要双指针系列第三篇相向双指针专题。三道题讲透比较、排除、收缩LC167 两数之和 II裸题一版过但这题的判决书有个反直觉的结构——淘汰 r 时论证的全部内容却是 l 的未来不动的那边才是死刑判决的依据LC11 盛最多水的容器排除论证的原题代码一次过、证明欠着的病历——“谁矮动谁凭什么安全矮边的所有剩余配对上限 ≤ 已记录值以及排序的自由度”LC15 的下标是身份标签、LC11 的下标是坐标LC15 三数之和boss四版弧线——把双指针写成递归回溯的六 if 平行惨案、“去重的宿主”回溯的同层剪枝不能字面搬家、li1的区间设计、以及第二个数可以和固定数同值的暗坑。相向双指针的全部灵魂一句话一次比较必须买到排除一整排候选的信息买不到就退化。前置阅读双指针与滑动窗口一框架总纲——三类问题、一个原理与判决书。配套代码仓库按题号分目录https://github.com/a18792721831/studyleetCode【算法】双指针与滑动窗口三相向双指针——比较、排除、收缩【算法】双指针与滑动窗口三相向双指针——比较、排除、收缩摘要1. 模板与识别信号2. 第一课 LC167裸题与不动的那边3. 第二课 LC11排除论证的原题3.1 代码一次过证明欠着3.2 排序的自由度4. 第三课 LC15boss 战的四版弧线4.1 第一版双指针写成递归回溯4.2 第二、三版空着没填和剪枝放错家4.3 终版收集 → 跳同值 → 双动 → continue4.4 三层去重地图 一个暗坑5. 相向双指针速查表总结参考资料1. 模板与识别信号l,r:0,len(nums)-1// 两端起步forlr{// 用有序性做一次 O(1) 比较// → 排除一整排候选l 的右半排 或 r 的左半排// → 只动一个指针}识别信号排序后找配对——两数之和、三数之和、区间极值。两个前提有序性是弹药排序给指针方向感和大 r–、和小 l、谁矮动谁——每次比较必须买到信息一轮一动每轮只动一个指针动作互斥。我在这上面栽过平行 if 无互斥四连犯最壮观的是 LC15 第一版——六行平行 if 递归同一轮指针同时走多条路2. 第一课 LC167裸题与不动的那边有序数组找两数之和等于 target下标从 1 返回。numbers [2,7,11,15], target 9→[1,2]。这题一版过代码六行forlr{ifnumbers[l]numbers[r]target{break}elseifnumbers[l]numbers[r]target{r--}else{l}}return[]int{l1,r1}值得记的是判决书的结构——淘汰 r 时论证的主体全在 l 身上sum target 时淘汰 r 的判决书 此后 l 只会右移有序⟹ 未来的 l 满足 nums[l] nums[l] ⟹ nums[l] nums[r] nums[l] nums[r] target ⟹ r 的所有剩余配对全部 target出局安全 sum target 淘汰 l 对称r 只会左移值只会更小反直觉的地方你淘汰 r却要盯着 l 的未来——因为不动的那边的单调性才是动的那边的死刑依据。这个结构后面两道题原样复用。两个小病历注释里残留右指针从中间开始的初始想法幸好没照做——拿[2,7,11,15]找 26 验证r 从中间起步l 一路右移追上 r漏掉 1115。错误想法留在注释里必须标注错在哪否则重读会被自己骗len2特判是化石l r循环天然覆盖。3. 第二课 LC11排除论证的原题盛最多水的容器。[1,8,6,2,5,4,8,3,7]→ 49。3.1 代码一次过证明欠着l,r:0,len(height)-1area:0forlr{areamax(area,min(height[l],height[r])*(r-l))ifheight[l]height[r]{// 谁矮动谁r--}else{l}}代码一次过但真正的考题是凭什么是矮的一边被淘汰假如最优解的边界恰恰是它呢拿[1,8,6,2,5,4,8,3,7]第一轮论证l0高 1、r8高 7当前面积 1×88。考察下标 0 作为左边界的所有可能它配任何 r’面积 min(1, height[r’]) × (r’-0) ≤ 1 × 8 8——高度被它自己卡死1宽度已经到头8它的所有剩余配对的上限就是刚刚记进 area 的这一格。它已经被代表过了除名绝对安全。对称地任何时候矮的一边都可以除名。这就是总纲篇那个统一原理的原始形态被淘汰的候选其所有剩余配对的上限 ≤ 已记录值。LC167 的和超了淘汰 r、LC3 的left 只进不退骨子里全是这一个论证——三道题一个灵魂。诚实记录这段证明是交卷后补的——代码一次过的那版注释里写的还是谁大选谁这种嘴瓢。代码能写对和能论证它对隔着看懂题解到能讲明白的距离。3.2 排序的自由度写这题时顺手记了一个观察“这个就不能排序了”。对照 LC15 很有意思——15 能排序是因为下标只是元素的身份标签无序随便换换个身份照样求和11 不能排序是因为下标是坐标宽度 下标差排序等于摧毁题面。排序的自由度取决于下标是否承载语义。这个判据后面在链表题里还会换装出现数组下标 O(1) 前驱 vs 链表节点无前驱先立个牌子。4. 第三课 LC15boss 战的四版弧线三数之和。[-1,0,1,2,-1,-4]→[[-1,-1,2],[-1,0,1]]。不重复O(n²)。思路本身不难排序 → 固定一个数 i → 内层用 LC167 找两数之和 -nums[i]——相向双指针的嵌套。难的全在工程。4.1 第一版双指针写成递归回溯手推指针演化表全对和小于 l、和大于 r–、同层剪枝动作全对然后代码写成了这个ifnums[l]nums[r]-nums[idx]{resappend(...);return}// 找到就撤 → 漏答案iflidx{backtrack(l1,r,idx)}// 六个 if 全部平行、ifridx{backtrack(l,r-1,idx)}// 各自递归、ifl0nums[l]nums[l-1]{...}// 互不 return ——ifsumtarget{backtrack(l,r-1,idx)}// 一轮走多条路ifsumtarget{backtrack(l1,r,idx)}外加一个初犯手推全程在排序数组上做代码里sort蒸发了。实测壮观原样传入输出[[2,-4,2]]同一个 2 被当固定数和 l 各用一次——元素复用[0,0,0]×4同一答案四条路径、九组大乱炖。病根一句话双指针的正确宿主是 for 循环。指针移动是互斥单步写成平行 if 递归等于同一轮指针同时走多条路。这版唯一值钱的是注释里的自问自答“为何答案有重复如果限制 lidx?”——它就是后面l i1的种子。4.2 第二、三版空着没填和剪枝放错家第二版骨架全对sort、外层剪枝、li1、for 循环两个残留找到答案return了该 l r-- 继续找——循环自带继续这正是双指针住 for 的原因内层去重没写——[-2,0,0,2,2]里下标不同、值相同的一对又凑出一次[-2,0,2]。第三版去填去重填成了这样ifsumtarget{收集;l;r--;continue}// 判定在前ifl1len(nums)nums[l]nums[l1]{l;continue}// ← 去重排在它后面实测依旧重复——去重一次都没执行到重复对每轮都在分支直接命中、append、continue排在后面的去重 if 根本没机会被走到。病根是把回溯同层剪枝的位置字面搬过来了它长在回溯每层的 for 里但双指针里去重的正确翻译是这个值已经配过对了收集完就把同值跳光——同一原则不同的家。4.3 终版收集 → 跳同值 → 双动 → continueforlr{sum:nums[l]nums[r]ifsum-nums[i]{resappend(res,[]int{nums[i],nums[l],nums[r]})forlrnums[l]nums[l1]{l}// 收集后立刻跳forlrnums[r]nums[r-1]{r--}lr--continue}ifsum-nums[i]{r--;continue}ifsum-nums[i]{l;continue}}为什么收集后敢整批跳同值——判决书是唯一性论证固定 i 和 l 之后能凑出 0 的搭档值是唯一确定的-nums[i]-nums[l]。同值的 l’ 再配任何搭档要么值不对凑不出 0要么值还是 nums[r]——但那已经是同一个三元组纯重复。跳同值就是在跳值层面已注定重复的候选。4.4 三层去重地图 一个暗坑位置手段相邻的坑固定数 ii0 nums[i]nums[i-1]跳过—内层 l收集后while nums[l]nums[l1] l第二个数可以和固定数同值内层 r收集后while nums[r]nums[r-1] r--同上暗坑值得单独一行[-1,-1,2]是合法答案——第二个数和固定数同值。如果把去重放在每轮开头看见同值就剪第一个被误杀的就是它我手推表里亲手剪掉过这个答案。收集后去重天然不误伤它只在这对已经成立之后才跳同值同角色的重复才被清理。还有那个值钱的小设计l i1——每个三元组只以其最小元素为固定数被发现一次值集合 (a≤b≤c) 与固定 a、在 a 右边找 b c一一对应第一版里lidx、ridx两个特判整个消失。特判是结构缺陷的补丁结构对了特判蒸发。5. 相向双指针速查表问题判据/口诀出处识别信号排序后找配对有序性是弹药每次比较必须买到排除一排的信息全类淘汰判决书主体是不动的那边它的单调性证明被淘汰者的剩余配对全灭≤ 或 ≥ 已记录/已判定值LC167/LC11排除论证模板被淘汰候选的所有剩余配对上限 ≤ 已记录值LC11能不能排序下标是身份标签可排是坐标不可排LC15 vs LC11宿主for 循环一轮一动、互斥分支收集后 continueLC15 四版去重的家收集之后跳同值不是每轮开头剪LC15固定数 内层双指针l 从 i1 起步消灭 idx 特判LC15同值暗坑第二个数可以和固定数同值——收集后去重天然不误伤LC15[-1,-1,2]手推工具指针演化表i / l / r / 和 / 动谁逐行推全类总结三道题一个动作循环比较、排除、收缩三个层次的收获判决书的镜像结构是相向双指针的核心直觉。淘汰谁就论证谁的对面——LC167 淘汰 r 时盯着 l 的单调未来LC11 淘汰矮边时算出矮边的配对上限。养成习惯每次动指针前先说出不动的那边保证了什么。原则不变宿主会变。同层去重从回溯带进双指针家从层循环开头搬到收集之后——字面搬家让剪枝成了永远执行不到的摆设。这和滑窗篇的断链套收缩是同一类病学新范式时最危险的不是新知识是旧知识的字面迁移。一次过不等于毕业。LC11 代码满分、证明欠着LC15 手推全对、代码另起炉灶。看懂题解和能讲明白之间的距离这个系列每篇都在量——量的工具就是判决书对着最险的一行讲出它为什么对。下一篇二分——找点与找边界两类模板与判定设计的三课。参考资料LeetCode 167. 两数之和 II - 输入有序数组LeetCode 11. 盛最多水的容器LeetCode 15. 三数之和LeetCode 718. 最长重复子数组双指针与滑动窗口一框架总纲——三类问题、一个原理与判决书双指针与滑动窗口二滑动窗口——吃进、判定、吐出版权声明本文为博主原创文章遵循 CC 4.0 BY-SA 版权协议转载请附上原文出处链接和本声明。