两数之和 II · 输入有序数组

怎样从“在升序数组 numbers=[2,7,11,15] 中找两个不同元素，使其和等于 target=9。输入保证非递减有序、唯一解、不能重复使用同一元素；返回 1-indexed 下标。”推导出 左右双指针 · 有序排除，并证明每次状态变化都不会漏掉答案？

中心结论：L、R 从两端向中间收缩：sum<target 时 R 已是当前最大值，numbers[L] 配最大值仍不够，可排除 L；sum>target 时 L 已是最小值，numbers[R] 配最小值仍超标，可排除 R。命中时返回 [l+1,r+1]。

找出两个数之和等于 target 的两个数字，要求输出它们的下标。注意一个数字不能使用 2 次。下标从小到大输出。假定题目一定有一个解。

在本站主例中，在升序数组 numbers=[2,7,11,15] 中找两个不同元素，使其和等于 target=9。输入保证非递减有序、唯一解、不能重复使用同一元素；返回 1-indexed 下标。

算法最终需要得到或观察：2+7=9，返回 1-indexed 下标 [1,2]（代码里 l=0,r=1）。

从每个位置重新搜索会重复走过同一片区域；双指针利用方向或有序性一次排除不可能部分。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“双向检查员”，明确答案需要观察什么。
2. 2状态只维护 左指针 L、右指针 R、numbers[L]、numbers[R]、当前和 sum、目标 target。
3. 3转移每一步按照 L、R 从两端向中间收缩：sum<target 时 R 已是当前最大值，numbers[L] 配最大值仍不够，可排除 L；sum>target 时 L 已是最小值，numbers[R] 配最小值仍超标，可排除 R。命中时返回 [l+1,r+1]。
4. 4收尾读取 2+7=9，返回 1-indexed 下标 [1,2]（代码里 l=0,r=1）。，并复核边界与复杂度。

每次移动都必须带着一个“被排除区域不可能含答案”的证明。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：左指针 L、右指针 R、numbers[L]、numbers[R]、当前和 sum、目标 target。

这一题比第 1 题 Two Sum 的问题还要简单，因为这里数组是有序的。可以直接用第一题的解法解决这道题。

L、R 从两端向中间收缩：sum<target 时 R 已是当前最大值，numbers[L] 配最大值仍不够，可排除 L；sum>target 时 L 已是最小值，numbers[R] 配最小值仍超标，可排除 R。命中时返回 [l+1,r+1]。

执行过程中持续维护：左指针 L、右指针 R、numbers[L]、numbers[R]、当前和 sum、目标 target。

正确性依赖以下不变量：若存在解，两个下标一定都落在闭区间 [L, R] 内。；每一步至少排除一个不可能元素；L 只增、R 只减，合计最多 n 次移动。

面试时可以压缩为：数组有序，我用左右双指针：sum<target 则 numbers[L] 与当前最大 R 相加仍不够，安全排除 L；sum>target 则 numbers[R] 与当前最小 L 相加仍超标，安全排除 R；相等则 return []int{l+1,r+1}。每步排除至少一个元素，O(n)/O(1)。

落到当前题，执行机制可以压缩为：L、R 从两端向中间收缩：sum<target 时 R 已是当前最大值，numbers[L] 配最大值仍不够，可排除 L；sum>target 时 L 已是最小值，numbers[R] 配最小值仍超标，可排除 R。命中时返回 [l+1,r+1]。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入在升序数组 numbers=[2,7,11,15] 中找两个不同元素，使其和等于 target=9。输入保证非递减有序、唯一解、不能重复使用同一元素；返回 1-indexed 下标。 因为：L、R 从两端向中间收缩：sum<target 时 R 已是当前最大值，numbers[L] 配最大值仍不够，可排除 L；sum>target 时 L 已是最小值，numbers[R] 配最小值仍超标，可排除 R。命中时返回 [l+1,r+1]。
2. 2有序数组 · L/R 落在两端非递减有序数组，L 指向最小值，R 指向最大值。返回 1-indexed 下标 [l+1,r+1]。 因为：数组有序时，[L,R] 内任意配对的和，被 a[L]+a[R] 与两端极值配对夹住；比较两端即可安全收缩。
3. 3排除 numbers[R]=15，R 左移排除 15（L 已是最小值仍超标），R 左移到 2。 因为：sum>target 时 L 已是当前最小值，numbers[R] 与任何 L 侧元素相加都超标，可安全排除 R。
4. 4预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。 因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
5. 5L=0, R=2, 2+11=13 > 9计算 numbers[L]+numbers[R]=13，与 target=9 比较。 因为：L=0 已是当前最小值 2，2+11=13>9，numbers[R]=11 不可能参与答案。
6. 6排除 numbers[R]=11，R 左移排除 11（L 已是最小值仍超标），R 左移到 1。 因为：sum>target 时 L 已是当前最小值，numbers[R] 与任何 L 侧元素相加都超标，可安全排除 R。
7. 7命中 2+7=9，返回 [1,2]命中：numbers[0]+numbers[1]=9，返回 [l+1,r+1]=[1,2]。 因为：代码里 l、r 是 0-indexed，LeetCode 要求返回 [l+1,r+1]；不要 return [l,r]。
8. 8收尾与复杂度2+7=9，返回 1-indexed 下标 [1,2]（代码里 l=0,r=1）。 因为：时间 O(n) · 空间 O(1)。L、R 从两端向中间收缩：sum<target 时 R 已是当前最大值，numbers[L] 配最大值仍不够，可排除 L；sum>target 时 L 已是最小值，numbers[R] 配最小值仍超标，可排除 R。命中时返回 [l+1,r+1]。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

// 解法一 这一题可以利用数组有序的特性
func twoSum(numbers []int, target int) []int {
	i, j := 0, len(numbers)-1
	for i < j {
		if numbers[i]+numbers[j] == target {
			return []int{i + 1, j + 1}
		}
		if numbers[i]+numbers[j] < target {
			i++
		} else {
			j--
		}
	}
	return nil
}

// 解法二 不管数组是否有序，空间复杂度比上一种解法要多 O(n)
func twoSum167_1(numbers []int, target int) []int {
	m := make(map[int]int)
	for i := 0; i < len(numbers); i++ {
		another := target - numbers[i]
		if idx, ok := m[another]; ok {
			return []int{idx + 1, i + 1}
		}
		m[numbers[i]] = i
	}
	return nil
}

func main() {
    // 1. 主例
    //    输入：mode="two-sum-sorted", array=[2,7,11,15], target=9
    //    期望：2+7=9，返回 1-indexed 下标 [1,2]（代码里 l=0,r=1）。
    //
    // 2. 失败 / 未命中
    //    检查：代码里 l、r 是 0-based，返回必须是 [l+1, r+1]，不要 return [l, r]。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC1 两数之和(哈希)；LC11 盛最多水的容器
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意在升序数组 numbers=[2,7,11,15] 中找两个不同元素，使其和等于 target=9。输入保证非递减有序、唯一解、不能重复使用同一元素；返回 1-indexed 下标。
2. 2重复从每个位置重新搜索会重复走过同一片区域；双指针利用方向或有序性一次排除不可能部分。
3. 3优化L、R 从两端向中间收缩：sum<target 时 R 已是当前最大值，numbers[L] 配最大值仍不够，可排除 L；sum>target 时 L 已是最小值，numbers[R] 配最小值仍超标，可排除 R。命中时返回 [l+1,r+1]。
4. 4证明若存在解，两个下标一定都落在闭区间 [L, R] 内。；每一步至少排除一个不可能元素；L 只增、R 只减，合计最多 n 次移动。
5. 5复杂度时间 O(n)，空间 O(1)