我试图解决对和问题，即给定一个排序数组，我们需要 如果存在两个索引i和j，以便i!=j和a[i]+a[j] == k某些k。
解决相同问题的方法之一是运行两个嵌套的for循环，从而导致O(n*n)的复杂性。
解决它的另一种方法是使用双指针技术。我无法使用两指针方法解决问题，因此查找了它，但我无法理解它为什么有效。我如何证明它有效？
#define lli long long
//n is size of array
bool f(lli sum) {
int l = 0, r = n - 1;
while ( l < r ) {
if ( A[l] + A[r] == sum ) return 1;
else if ( A[l] + A[r] > sum ) r--;
else l++;
}
return 0;
}
好吧，可以这样想：
你有一个排序数组(你没有提到数组是排序的，但对于这个问题，通常是这种情况)：
{ -1,4,8,12 }
该算法首先选择数组中的第一个元素和最后一个元素，将它们相加并将它们与您所需的总和进行比较。
如果我们的初始总和与我们正在寻找的总和相匹配，那就太好了！！ 如果没有，那么我们需要继续研究大于或小于我们开始时的总和的可能总和。 通过从数组中最小值和最大值开始计算初始总和，我们可以消除其中一个元素作为可能解决方案的一部分。
假设我们正在寻找总和 3。 我们看到 3 <11。 由于我们的大数 (12) 与尽可能小的数字 (-1) 配对，因此我们的总和太大的事实意味着 12 不能成为任何可能解决方案的一部分，因为任何其他使用 12 的总和都必须大于 11(12 + 4> 12 - 1、12 + 8> 12 - 1)。
所以我们知道我们不可能用数组中的 12 + 另一个数字做一个 3 的总和;它们都太大了。 因此，我们可以通过向下移动到下一个最大的数字 8 来从搜索中消除 12。 我们在这里做同样的事情。 我们看到 8 + -1 仍然太大，所以我们向下移动到下一个数字 4，瞧！ 我们找到匹配项。
如果我们得到的总和太小，同样的逻辑也适用。我们可以消除我们的小数，因为我们使用当前最小数获得的任何总和都必须小于或等于我们与当前最大数配对时得到的总和。
我们一直这样做，直到找到匹配项，或者直到索引相互交叉，因为在它们交叉之后，我们只是将我们已经检查过的数字对相加(即 4 + 8 = 8 + 4)。
这可能不是一个数学证明，但希望它能说明算法是如何工作的。
Stephen Docy在追踪程序的执行并解释其决策背后的基本原理方面做得很好。也许让答案更接近算法正确性的数学证明可以更容易地推广到像 zzzzzzz 在评论中提到的问题。
我们得到一个长度为n的排序数组A和一个整数sum。我们需要找出是否有任何两个索引i和j，以便i != j和A[i] + A[j] == sum。
解决方案(i, j)和(j, i)是等价的，因此我们可以假设i < j不会失去一般性。在程序中，i的当前猜测称为l，j的当前猜测称为r。
我们迭代地对数组进行切片，直到找到一个切片，该切片的两个总和在其边界处sum，或者我们发现没有这样的切片。切片从索引l开始，到索引r结束，我将它写为(l, r).
最初，切片是整个数组。在每次迭代中，切片的长度减少 1：左边界索引l增加或右边界索引r减少。当切片长度减小到1(l == r)时，切片内没有不同的索引对，因此返回false。这意味着算法会因任何输入而停止。O(n)的复杂性也立即清晰。正确性仍有待证明。
我们可以假设有一个解决方案;如果没有，则上一段中的分析适用，并且返回 true 的分支永远不会被执行。
循环有一个不变的(无论已经完成了多少次迭代，该语句都成立)：当解决方案存在时，它要么(l, r)自身，要么是其子切片。在数学上，这样的不变量是一个引理——它本身不是很有用，但却是整体证明的垫脚石。我们通过最初(l, r)整个数组并观察每次迭代使切片更短，不变性确保我们最终会找到解决方案来获得整体正确性。现在，我们只需要证明不变量。
我们将通过归纳来证明不变性。感应基底是微不足道的——初始切片(l, r)要么是溶液，要么将其作为子切片包含。困难的部分是归纳步骤，即证明当(l, r)包含解决方案时，要么是解决方案本身，要么是下一次迭代的切片包含作为子切片的解。
-
当
A[l] + A[r] == sum时，(l, r)是解决方案本身;循环中的第一个条件被触发，true被返回，每个人都很高兴。 -
当
A[l] + A[r] > sum时，下一次迭代的片是(l, r - 1)，它仍然包含解。让我们通过矛盾来证明这一点，假设(l, r - 1)不包含解决方案。当(l, r)包含解决方案(通过归纳假设)时，这怎么会发生？唯一的方法是解决方案(i, j)具有j == r(r是我们从切片中删除的唯一索引)。因为根据定义A[i] + A[j] == sum，我们在这个分支中得到A[i] + A[r] == sum < A[l] + A[r]。当我们从不平等的两边减去A[r]时，我们得到A[i] < A[l]。但是A[l]是(l, r)切片中的最小值(数组是排序的)，所以这是一个矛盾。 -
A[l] + A[r] < sum时，下一次迭代的切片(l + 1, r)。该参数与前一种情况对称。
∎
该算法可以很容易地重写为递归算法，从而以牺牲实际性能为代价简化分析。这就是函数式编程方法。
#define lli long long
//n is size of array
bool f(lli sum) {
return g(sum, 0, n - 1);
}
bool g(lli sum, int l, int r) {
if ( l >= r ) return 0;
else if ( A[l] + A[r] == sum ) return 1;
else if ( A[l] + A[r] > sum ) return g(sum, l, r - 1);
else return g(sum, l + 1, r);
}
f函数仍包含初始化，但它调用新的g函数，该函数实现原始循环。它不是将状态保留在局部变量中，而是使用其参数。g函数的每次调用对应于原始循环的一次迭代。
g函数是比原始函数更普遍的问题的解决方案：给定一个排序数组 A，是否有任何两个索引i和j，使得i != j和A[i] + A[j] == sum以及i和j都在l和r(包括)之间？
这使得阅读分析变得更加简单。循环不变量实际上是g正确性的证明，g的结构指导证明。