1回答

liuyubobobo

2021-03-23

已采纳

因为 i 是从 i - 1 的地方过来的。和 i - 1 相关的数据对，在之前肯定已经考察过了。

最初， i = 0， j = n - 1，表示，能够让 arr[i] + arr[j] == target 的 (i, j) 数据对，在 [0, n - 1] 这个区间中。

如果看到 arr[i] + arr[j] > target，j -- 的意思是，当前的 j 已经考虑完了，我们可以考虑新的 j 了。也就是 j 和 i 右的其他的数据对，我们已经不用看了。因为 arr[i] + arr[j] 已经大于 target 了，i 右侧的值 + arr[j] 肯定更大于 target，j --，相当于说，[i, j - 1] 范围里还有可能有解。

如果看到 arr[i] + arr[j] < target，i ++的意思是，当前的 i 已经考虑完了，我们可以考虑新的 i 了。也就是 i 和 j 左侧的其他的数据对，我们已经不用看了。因为 arr[i] + arr[j] 已经小于 target 了，j 左侧的值 + arr[i] 肯定更小于 target。i ++，相当于说，[i + 1, j] 范围里还有可能有解。

i 不会 -1，j 也不会 +!。因为我们每扔掉一个 i，和 i 组成的数据对已经考察完了；每扔掉一个 j，和 j 组成的数据对也已经考察完了。

我们是在按照这个逻辑，逐渐缩小解的可能范围。每次 i ++ 或者 j --，相当于一次性地扔掉了很多数据对不再检查了（而不是暴力搜索那样一次只决定了一个数据对）。

==========

依然是，我建议你看一下 11 号问题，看一下 11 号问题的双指针解法。然后看一下我这里的证明：https://mp.weixin.qq.com/s?__biz=MzU4NTIxODYwMQ==&mid=2247485456&idx=1&sn=b2b034a44c4b13c1f6ef7a7ff742db0e&chksm=fd8ca756cafb2e407aa79c1c81c944e9d3332aba17a7e66d4739d80b65ff9b95c01b7170759b&token=1717627806&lang=zh_CN#rd

再和我上面描述的证明做一下对比。二者的思路是完全一致的。

继续加油！：）

0

1

许昭宇

想明白了，谢谢老师。

2021-03-23

共1条回复