你这么想吧
你有一个排序的数组（你没有提到数组是排序的，但对于这个问题，通常是这样的）：
{-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做了一个伟大的工作 * 跟踪 * 程序的执行，并解释其决策背后的基本原理。也许让答案更接近于算法正确性的数学证明，可以更容易地推广到评论中的the one mentioned by 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的分支。
这个循环有一个 invariant（不管已经迭代了多少次，这个语句都是真的）：**当一个解存在时，它要么是(l, r)本身，要么是它的子切片。在数学上，这样一个不变量是一个引理--它本身不是很有用，但在整个证明中是一块垫脚石。我们通过最初使(l, r)成为整个数组并观察到随着每次迭代使切片变短，不变量确保我们最终会找到解决方案来获得整体正确性。现在，我们只需要证明不变量。
我们将用归纳法证明这个不变量。归纳基是平凡的--初始切片(l, r)要么是解，要么包含它作为子切片。困难的部分是诱导步骤，即证明当(l, r)包含解时，要么它是解本身，要么下一次迭代的切片包含解作为子切片。
1.当A[l] + A[r] == sum时，(l, r)是解本身;循环中的第一个条件被触发，返回true，每个人都很高兴。
1.当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)切片中最小的值（数组是排序的），所以这是一个矛盾。
1.当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之间（包括l和r）？
这使得阅读分析更加简单。循环不变量实际上是g正确性的证明，g的结构指导了证明。