[!info] related notes

• 双指针
• 无序数组两数之和
• 算法面试题型 MOC

LCR 006 两数之和 II

本文保留原题链接 LCR 006，输入为非递减整数数组，答案返回从 0 开始的下标。例如 [1, 2, 4, 6, 10]、目标 8 返回 [1, 3]。

同名的 LeetCode 167 要求一基下标，复用下面算法时需将返回值改为 [left + 1, right + 1]。两题算法相同，输出契约不同。

双指针实现

function twoSum(numbers: number[], target: number): number[] {
    let left = 0;
    let right = numbers.length - 1;

    while (left < right) {
        const sum = numbers[left] + numbers[right];

        if (sum === target) {
            return [left, right];
        }
        // 利用数组有序的特性：
        // 如果和太大，收缩右边界；如果和太小，增加左边界。
        sum > target ? right-- : left++;
    }

    return []; // 题目保证有解；空数组表示契约之外的无解输入
}

数组有序时，和过小就右移左指针，和过大就左移右指针；被排除的端点不能与区间内其他元素组成目标和。每次至少移动一个指针，时间 O(n)，额外空间 O(1)。