LeetCode 754. 到达终点数字
题目描述
题意分析
从零出发，第
i次移动的距离固定为i，只能选择向左还是向右，求到达target的最少移动次数。方向可以逐步独立选择，不要求途中始终靠近目标。把每一步的方向全部反转，就会把终点从
target变为-target，步数不变。因此正负目标的答案相同，可以先取绝对值，只讨论非负目标。
解法：等差和 + 奇偶性
核心思路
[!blue]
假设走了
k步且全部向右，能到达的最远位置是 $S = 1 + 2 + \cdots + k$。把第i步从向右改为向左，会把总位移从增加i变成减少i，也就是让终点减少2 * i。如果被翻转的步长之和为
x，最后位置就是S - 2 * x。要到达目标，必须有S >= target，且S - target为偶数；此时只需选出和为(S - target) / 2的若干步长进行翻转。这两个条件也足够，因为
1到k的子集和能覆盖从0到S的每个整数。可以归纳证明：设1到k - 1已覆盖[0, S']，不选k时仍能得到这个区间，选k时能得到[k, k + S']。由于k <= S' + 1，两个整数区间相接或重叠，合起来恰好覆盖[0, S' + k]。所需翻转和落在这个范围内，因此一定能够选出。代码从零步开始依次增加
k和sum，始终保持sum是前k步的总和。只要距离不足或差值为奇数，就继续增加下一步；第一次同时满足两个条件时，当前步数可行，而此前所有步数都不可行，所以它就是最小答案。总和第一次达到目标后，若差值仍为奇数，至多再走两步就够：下一步步长为奇数时会直接改变差值奇偶性；若它为偶数，则再下一步必为奇数。这样也说明循环一定结束，且主要步数由三角和达到目标决定。
解题步骤
- 目标取绝对值。
- 步数与总和从零开始。
- 总和不足或差为奇数时，增加下一步。
- 第一次同时满足条件的步数就是答案。
只需判断是否存在翻转集合，不必实际构造它。题目给定的目标绝对值不超过 $10^9$，取绝对值以及累计到首次满足条件时的总和都在
int范围内。奇偶条件可能随步数来回变化，不能把完整可行性当成单调条件直接二分。
代码实现
class Solution {
public int reachNumber(int target) {
target = Math.abs(target);
int sum = 0;
int k = 0;
// 既要走得够远，也要使翻转所需差额为偶数
while (sum < target || (sum - target) % 2 != 0) {
// 先增加下一步步长，再计入对应三角和
k++;
sum += k;
}
return k;
}
}
func reachNumber(target int) int {
if target < 0 {
target = -target
}
sum := 0
k := 0
// 既要走得够远，也要使翻转所需差额为偶数
for sum < target || (sum-target)%2 != 0 {
// 先增加下一步步长，再计入对应三角和
k++
sum += k
}
return k
}
复杂度分析
- 时间复杂度：$O(\sqrt{\lvert target\rvert+1})$，达到距离下界后再补至多两步即可调整奇偶。
- 空间复杂度：$O(1)$，总和与步数。
关键点总结
[!green]
- 完整可行条件对步数并不单调，不能把奇偶直接塞进普通二分。
- 翻转贡献变化是二 i，不是一 i。
易错点总结
[!yellow]
- 只等总和超过目标就停，会漏掉奇偶限制。
- 先加旧步数再自增，会让总和与步数错位。
- 不取绝对值，会错误处理负目标的距离下界。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 494. 目标和 | 中等 | 同样选择正负号达到目标，本题使用1到k并求最小k，可用总和与目标差的奇偶性判断。 |
| 441. 排列硬币 | 简单 | 同样利用连续整数和确定最小或最大层数，本题在达到目标绝对值后还要满足奇偶条件。 |