关于老师的例题中对撞指针的疑问
来源：3-6 对撞指针 Two Sum II - Input Array is Sorted
JAVA你是偶滴神
2023-01-07
对撞指针的写法没有回溯，说明它没法遍历所有的组合可能性，那么正确解一定会出现在它所找的这些可能中吗？这点我不知道如何证明。因为假设这对对撞指针l和r已经都遍历了一些位置，那么此时l+r>target的话，对撞指针的做法是r--，那其实这个时候l--也可以降低二者的和，所以应该如何证明对撞指针遍历过的不符合的那些数最后肯定不会是正解？（假设这个问题只有唯一解）
写回答
1回答
-
liuyubobobo
2023-01-07
非常好的问题。
简单说明一下为什么 left -- 不可能得到解：
因为，left -- ，即再去看 left - 1，相当于再访问一个之前访问过的左边界索引上。
但是在之前访问 left - 1 的时候，如果 arr[left - 1] + arr[right] > target，会 right -- 继续去找解。那么这个过程一定已经找到这个解了。只有在 arr[left - 1] + arr[right] < target 的时候，也就是在 left - 1 的时候肯定不会再有解的时，left - 1 才会右移，去看 left。
换句话说，当我们看到 left 的时候，相当于已经明确了，左边界在 [0, left - 1] 区间的时候，肯定没有解了。（否则 left 走不到现在的位置，已经找到解了。）
继续加油！：）
112023-01-07
相似问题