关于老师的例题中对撞指针的疑问

Question

对撞指针的写法没有回溯，说明它没法遍历所有的组合可能性，那么正确解一定会出现在它所找的这些可能中吗？这点我不知道如何证明。因为假设这对对撞指针l和r已经都遍历了一些位置，那么此时l+r>target的话，对撞指针的做法是r--，那其实这个时候l--也可以降低二者的和，所以应该如何证明对撞指针遍历过的不符合的那些数最后肯定不会是正解？（假设这个问题只有唯一解）

Answer 1

liuyubobobo 2023-01-07 15:53:42

非常好的问题。

简单说明一下为什么 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 走不到现在的位置，已经找到解了。）

继续加油！：）

• 提问者 JAVA你是偶滴神 #1

  谢谢波波老师！明白了，茅塞顿开！我看课的时候纠结了半天没想明白