面试题57（一）：和为s的两个数字

从“最小值加最大值”开始

先预测：递增数组1、2、4、7、11、15中寻找和为s的两个数字，s为15。最左端1与最右端15的和为16，已经偏大；若固定15，再把左端换成更大的2、4或7，只会更大，因此15不可能参与答案，可以直接删掉最右端。

作者用首尾双指针。behind从0开始，ahead从length减1开始，两者之间形成窗口。

每轮只比较当前两端之和：偏小就增加最小端，偏大就减小最大端，恰好相等就返回。这就是根据当前和移动边界。

排序为何允许整批排除（单调性）

输入是递增排序数组。当前和小于s时，behind指向区间内最小值；它与最大值ahead相加仍不足，与任何更小右端搭配更不可能达到s，因此当前behind可以永久删除。

当前和大于s时，ahead指向区间内最大值；它与最小值behind相加仍过大，与任何更大左端搭配只会更大，因此当前ahead可以永久删除。

这种由有序性证明一整批组合不可能、并只移动一个边界的过程称为。

若当前和相等，两个指针满足ahead大于behind，必然对应两个不同数组位置。作者题面允许有多对解时输出任意一对，所以无需继续搜索。

手算作者Test1

数组1、2、4、7、11、15，目标15：

1. 1加15等于16，偏大，ahead从15移到11。
2. 1加11等于12，偏小，behind从1移到2。
3. 2加11等于13，偏小，behind从2移到4。
4. 4加11等于15，命中并返回。

两个指针每次至少一个向内移动，从不回退。每个位置最多成为一次边界，所以总比较次数不超过线性数量。

忠实还原作者接口

作者返回bool表示是否找到，只在成功分支写num1与num2。

bool FindNumbersWithSum(
    int data[],
    int length,
    int sum,
    int* num1,
    int* num2) {
    bool found = false;
    if (length < 1 ||
        num1 == nullptr ||
        num2 == nullptr) {
        return found;
    }
 
    int ahead = length - 1;
    int behind = 0;
 
    while (ahead > behind) {
        long long curSum =
            data[ahead] + data[behind];
 
        if (curSum == sum) {
            *num1 = data[behind];
            *num2 = data[ahead];
            found = true;
            break;
        } else if (curSum > sum) {
            --ahead;
        } else {
            ++behind;
        }
    }
    return found;
}

while使用ahead大于behind，而不是大于等于，确保不能拿同一个元素与自己配对。这是约束。

例如数组只有一个3、目标6时返回false；数组有两个3、目标6时两个指针位于不同下标，可以返回3和3。

找不到时输出保持原样

长度小于1或任一输出指针为空时返回false。循环直到指针相遇仍未命中也返回false。所有失败路径都不写num1和num2。

调用方必须先检查bool，再读取输出。作者Test函数声明未初始化的num1、num2，但只在result为true时求和，因此安全；若失败后日志仍打印两个值，就会读取未初始化对象。

源码没有显式检查data。Test4传nullptr时length为0，长度判断先返回，所以安全；若data为空但length为2，循环会解引用空指针。指针与长度必须作为一个一致的内存范围由调用方保证。

length为1不满足入口的“小于1”，但ahead与behind都为0，循环不进入并返回false，不会读取data。更清晰的入口可以直接拒绝length小于2。

long long声明仍未完全防溢出

源码把curSum声明为long long，但右侧data[ahead]与data[behind]都是int。C++先按int执行加法，再把结果转换为long long；若两个int之和越界，溢出发生在转换之前。

作者sum参数仍是int，因此接口只能查询int可表示的目标。现代版可同时提升输入比较和目标类型，并用optional表达失败。

#include <cstdint>
#include <optional>
#include <span>
#include <utility>
 
std::optional<
    std::pair<std::int32_t, std::int32_t>>
findNumbersWithSum(
    std::span<const std::int32_t> data,
    std::int64_t target) {
    if (data.size() < 2) {
        return std::nullopt;
    }
 
    std::size_t left = 0;
    std::size_t right = data.size() - 1;
    while (left < right) {
        const std::int64_t current =
            static_cast<std::int64_t>(
                data[left]) +
            static_cast<std::int64_t>(
                data[right]);
 
        if (current == target) {
            return std::pair{
                data[left], data[right]};
        }
        if (current < target) {
            ++left;
        } else {
            --right;
        }
    }
    return std::nullopt;
}

span把指针和长度绑定，const视图表明算法不修改数组。optional不存在时没有可误读的输出槽。

任意一对不是全部数对

作者明确允许多对时输出任意一对，这种语义让首次命中即可停止。

例如1、2、3、4、5、6目标7有1与6、2与5、3与4三对，作者从两端开始会先返回1与6。它不承诺乘积最小、差值最小、字典序最小或下标最早。

若要求枚举全部不同值对，命中后要同时移动两端并跳过重复值；若要求所有下标组合，重复值还要按频次展开，输出规模本身可能达到O(n平方)。不能只删掉break就声称完成全部枚举。

输出值而非下标也很重要。若调用方要求原始下标，先排序会打乱位置，需要连同原下标排序或改用哈希。

无序数组应换方法

双指针正确性依赖排序。无序数组中当前左端不一定最小、右端不一定最大，移动边界无法证明排除安全。

若允许修改或复制后排序，成本为O(n log n)，再双指针O(n)；若必须保持原顺序并需要原下标，可用哈希表记录已见值。

#include <optional>
#include <unordered_map>
#include <utility>
#include <vector>
 
std::optional<std::pair<int, int>>
findIndicesWithSum(
    const std::vector<int>& values,
    int target) {
    std::unordered_map<int, int> seen;
    for (int index = 0;
         index < static_cast<int>(
             values.size());
         ++index) {
        const int needed =
            target - values[index];
        if (auto it = seen.find(needed);
            it != seen.end()) {
            return std::pair{
                it->second, index};
        }
        seen.emplace(values[index], index);
    }
    return std::nullopt;
}

这版平均O(n)时间、O(n)空间，但target减value也可能int溢出，严格工程版同样应使用更宽类型。哈希迭代顺序和重复覆盖策略还会影响多解时返回哪一对。

正确性与终止

循环不变式是：若某个合法对尚未找到，它的两个下标仍位于behind到ahead之间。偏小删除behind、偏大删除ahead的证明保证不变式保持。

每轮严格增加behind或减小ahead，有限数组中两者最终命中或相遇，所以循环必然终止。相遇时区间内不足两个不同下标，不可能再有合法对，返回false正确。

时间O(n)，额外空间O(1)。这不包含输入排序成本，因为作者契约已经给出递增数组；若函数内部排序，复杂度和是否修改输入都必须重新说明。

重复值不破坏非递减单调性。只要数组按值有序，移动证明仍成立；严格递增不是算法必要条件，但两个相同值必须有两个独立位置才能成对。

还可以把所有下标对想成一张和矩阵：行下标增大时左值不减，列下标增大时右值不减。双指针从“最小左值加最大右值”的右上边界出发，和偏大向左走，偏小向下走，沿一条阶梯路径最多移动两倍数组长度。ahead大于behind只保留矩阵上三角区域，避免同一下标和镜像重复组合。这个视角也解释了为何算法是O(n)而不是枚举O(n平方)个格子。

如果同一排序数组要查询很多不同目标，作者算法对每个目标仍需最坏O(n)，q次是O(qn)。可预建值到下标列表的哈希索引，以O(n)空间换取每次平均扫描较少或成员查询；也可对每个左值二分补数，单次O(n log n)，通常不如双指针。只有目标批量很大、需要原下标或数据分布允许专门索引时，预处理才可能抵消维护成本。

数组若会更新，排序前提也有维护代价。插入一个新值到连续数组需要移动元素，哈希则更易增量更新；平衡搜索树可保持有序但双端遍历和重复值管理更复杂。算法选择应包含数据生命周期，而不只比较一次查询的渐进式。

作者4组测试逐项还原

1. 1、2、4、7、11、15，目标15，答案4与11位于中间，返回true。
2. 1、2、4、7、11、16，目标17，答案1与16位于两端，返回true。
3. 同一数组目标10，没有合法对，指针相遇后返回false。
4. nullptr、长度0、目标0，由长度检查直接返回false。

作者成功测试只验证num1加num2等于目标，不固定具体数对；这与任意一对语义一致。失败测试不读取输出。

#include <cassert>
 
void testTwoNumbersWithSum() {
    int middle[] = {1, 2, 4, 7, 11, 15};
    int endpoints[] =
        {1, 2, 4, 7, 11, 16};
 
    int first = 0;
    int second = 0;
    assert(FindNumbersWithSum(
        middle, 6, 15,
        &first, &second));
    assert(first + second == 15);
 
    assert(FindNumbersWithSum(
        endpoints, 6, 17,
        &first, &second));
    assert(first + second == 17);
 
    first = 123;
    second = 456;
    assert(!FindNumbersWithSum(
        endpoints, 6, 10,
        &first, &second));
    assert(first == 123 &&
           second == 456);
 
    assert(!FindNumbersWithSum(
        nullptr, 0, 0,
        &first, &second));
}

随机对拍可生成排序数组和随机目标，用O(n平方)二重循环参考判断是否存在。作者版返回true时验证两个值来自不同可用位置且和正确；返回false时参考也必须无解。

还应加入两个相同值、多个解、整数极值和data为空但正长度的契约测试。最后一种不应实际调用原函数解引用，而应由包装层预先拒绝。

本章练习

本章回顾

1. 和为s的两个数字在递增排序数组中可用首尾双指针查找。
2. 当前和偏小就左移，偏大就右移，相等返回任意一对。
3. 单调排除保证被删除边界不可能参与剩余答案。
4. ahead严格大于behind，确保使用两个不同下标。
5. 作者失败时返回false且不写输出，调用方不能读取旧值。
6. long long接收int加法仍可能先溢出，必须先提升操作数。
7. 多解只返回首次命中；全部数对是不同输出规模的问题。
8. 无序输入应先排序或使用哈希，不能直接套双指针。

名词解释