LeetCode 754. 到达终点数字

2022-10-25 HGNULB 约 10 分钟

文章信息 7 个分类 2 个标签

分类

题目描述

✅ 754. 到达终点数字

题意分析

从数轴原点出发，第 $i$ 次移动必须走恰好 $i$ 步（第一次走 $1$，第二次走 $2$，以此类推），每次可以自由选择向左还是向右，但步长不能跳过也不能重复。问最少移动多少次才能正好落在 target 上。

题面有三条信息值得单独拎出来。第一，步长是固定递增的，唯一的自由度只有每一步的方向，所以「走了 $k$ 次」这件事完全决定了可用的步长集合 ${1, 2, \dots, k}$。第二，要求恰好落在 target，不能超过再退回来算数（退回来本身也要消耗步数）。第三，问的是最小次数，说明答案关于 $k$ 有某种单调可判定的性质。

数轴关于原点对称，向左走和向右走完全等价，所以 target 的正负不影响答案，第一步就应该取绝对值把问题归一化到正半轴。题目给的范围是 $-10^9 \le target \le 10^9$ 且 target != 0，取绝对值后不超过 $10^9$，而 $1 + 2 + \dots + k \approx \frac{k^2}{2}$，所以 $k$ 大约在 $\sqrt{2 \times 10^9} \approx 45000$ 量级——这个规模说明「从小到大逐个试 $k$」是完全可行的，不需要解一元二次方程。

边界上要覆盖：target 为负（必须先取绝对值，否则循环条件恒不成立）；target = 1（答案是 $1$）；target = 2（$1 + 2 = 3$ 超了但差 $1$ 是奇数，$1+2+3 = 6$ 差 $4$ 是偶数，答案是 $3$）；target 恰好等于某个三角形数（如 $3 = 1 + 2$，一步不多）；target 极大时的累加溢出（$k$ 到 $45000$ 时 sum 约 $10^9$，int 够用但要确认不会失控）。

解法：等差和 + 奇偶性

核心思路

暴力做法是搜索：每一步枚举向左或向右，走到第 $k$ 步时检查位置是否等于 target。状态空间是 $2^k$，即使配上剪枝也无法接受，而且不容易判定何时该停。

瓶颈在于把「方向选择」当成了需要搜索的组合问题。观察一下走完 $k$ 步之后的位置：如果全部向右，位置是 $S_k = 1 + 2 + \dots + k = \frac{k(k+1)}{2}$。现在把其中某一步 $i$ 从向右改成向左，位置的变化不是 $-i$ 而是 $-2i$——因为它从「贡献 $+i$」变成了「贡献 $-i$」，净变化是 $2i$。

这就给出了核心结论：走 $k$ 步能到达的所有位置，恰好是 $S_k$ 减去某个「翻转集合之和的两倍」，也就是 $S_k - 2m$，其中 $m$ 可以是 $0$ 到 $S_k$ 之间的任意整数（因为 ${1, 2, \dots, k}$ 的子集和能取遍 $[0, S_k]$ 里的每一个整数，这是连续自然数集合的特性）。于是走 $k$ 步能到达 target 当且仅当两个条件同时成立：

可达性下界：$S_k \ge target$。翻转只会让位置变小，所以最远也就是 $S_k$，走不到比它更远的地方。

奇偶性匹配：$S_k - target$ 是偶数。因为差额必须写成 $2m$ 的形式，奇数差额无论怎么翻转都补不上。

这两条合起来把一个指数级搜索压成了对 $k$ 的一维判定。于是维护的不变量是：循环中的 k 是当前尝试的步数，sum 恒等于 $1 + 2 + \dots + k$；只要 sum < target 或 (sum - target) 为奇数，就说明 k 步不可行，需要继续增大。

为什么可以从小到大逐个试而不会错过更小的答案？因为条件是逐个 $k$ 独立判定的，第一次同时满足两条的 $k$ 自然就是最小的。而且不必担心循环跑不完：一旦 $S_k \ge target$，后续每加一步 $S_k$ 的奇偶性会按「奇、奇、偶、偶」的周期变化，因此从任意位置出发最多再走 $3$ 步就一定能碰到一个奇偶匹配的 $k$，循环必然终止。

这也解释了为什么不需要真的构造出翻转方案——题目只问次数，而可达性判定已经是充要条件了。

解题步骤

第一行把 target 取绝对值。理由：数轴关于原点对称，把每一步的方向整体取反就能把负目标映射成正目标，步数完全相同；不取绝对值的话，sum < target 对负数恒不成立，循环会立刻退出并返回 $0$。

初始化 sum = 0、k = 0。理由：$k = 0$ 时一步没走，位置就是原点，$S_0 = 0$，这个初值让不变量 sum == k*(k+1)/2 从一开始就成立；同时它天然覆盖了「还没开始走」的状态。

循环条件写成 sum < target || (sum - target) % 2 != 0。理由：这是把「不可行」的两种情形用 || 合起来——要么还没走够远，要么走够了但奇偶不匹配；只要还落在不可行区就继续增加步数。两个条件的顺序无所谓，但都必须有，缺任何一个都会得到错误答案。

循环体里先 k++ 再 sum += k。理由：这两句合起来把 $S_{k-1}$ 推进成 $S_k$，维持了 sum 与 k 的对应关系；顺序反过来（先 sum += k 再 k++）会让 sum 少加一次，不变量被破坏。

循环退出后直接返回 k。理由：退出意味着两个条件都不满足，即 sum >= target 且差为偶数，此时 $k$ 步一定可达，且由于是从小到大第一次满足，它就是最小值。

注意 (sum - target) % 2 != 0 而不是 == 1。理由：虽然本题中 sum >= target 时差非负，写 == 1 也能过，但在 sum < target 的轮次里差是负数，Java 和 Go 的取模会得到 $-1$，== 1 判定为假会让条件退化，写 != 0 才是无论正负都正确的奇偶判断。

以 target = 2 走一遍。取绝对值后仍是 $2$，sum = 0、k = 0。第一轮判定：sum(0) < 2 成立，进入循环，k = 1、sum = 1。第二轮判定：sum(1) < 2 成立，k = 2、sum = 3。第三轮判定：sum(3) < 2 不成立，但 3 - 2 = 1，1 % 2 != 0 成立（奇偶不匹配），继续，k = 3、sum = 6。第四轮判定：sum(6) >= 2 且 6 - 2 = 4 是偶数，两条都不满足，退出，返回 $3$。验证一下：三步可以走成 -1 + 2 + ... 不对，正确的是 $+1 -2 +3 = 2$，也就是把第二步翻转，翻转量 $m = 2$，差额 $6 - 2 = 4 = 2m$，与推导完全吻合。再用 target = 3 走一遍：k = 1 时 sum = 1 < 3 继续；k = 2 时 sum = 3，不小于 $3$ 且差为 $0$ 是偶数，退出返回 $2$，对应 $+1 +2 = 3$ 一步都不用翻转。

代码实现

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{target})$。循环每轮把 sum 增加 k，要让 sum 达到 target 大约需要 $k \approx \sqrt{2 \cdot target}$ 轮；达到之后由于奇偶性以 $4$ 为周期变化，最多再多跑 $3$ 轮就会命中。$target \le 10^9$ 时循环次数不超过约 $45000$，每轮只做常数次算术运算。

空间复杂度：$O(1)$。只用了 sum 和 k 两个整型变量，没有任何数组、递归或辅助结构；sum 的最大值约为 $target + 2\sqrt{target}$，在 $10^9$ 量级内，int 不会溢出。

关键点总结

「每一项的符号可自由选择」的问题，要立刻把它转化成「先全取正，再翻转某个子集」的模型。翻转一项 $i$ 的净效果是 $-2i$，于是可达位置集合就是 ${S - 2m}$，这一步把方向搜索变成了数论判定。同样的思路适用于「数组添加正负号使和为目标值」这类题。

当元素是连续自然数 $1, 2, \dots, k$ 时，其子集和能取遍 $[0, S_k]$ 的每一个整数——这是关键的完备性引理，正因为它成立，才能断言「只要 $S_k \ge target$ 且奇偶匹配就一定可达」。换成任意数组这条就不成立了，必须小心区分。

奇偶性（更一般地是模某个数的同余）是判定「差额能否被补齐」的标准工具。看到「每次操作改变量恒为偶数」时，就该立刻检查目标差额的奇偶性。

循环终止性要能说清楚：$S_k$ 的奇偶序列以 $4$ 为周期呈「奇奇偶偶」，所以越过下界后最多再走 $3$ 步必然命中。能说出这个「最多 +3」的结论，说明真的分析过而不是碰运气。

对称性归一化（取绝对值）是消除分支的常用手段，代价只有一行，却能让后续所有推理只面对正数。

面试视角：字节和网易考这题是想看能否把搜索问题化归为数学判定。理想的作答是先说「方向选择等价于翻转子集，翻转 $i$ 的净变化是 $-2i$」，再给出两条充要条件，最后说明「从小到大试 $k$，最多多走三步」。写完可以顺带提一句「也能用一元二次方程直接解出 $k$ 的下界再向上微调，但循环写法更短且不涉及浮点误差」——这既展示了你知道二分/公式解法，又说明了选型理由。

易错点总结

错误写法：忘记对 target 取绝对值 → 用例 target = -3 → sum(0) < -3 不成立，(0 - (-3)) % 2 = 1 != 0 成立所以还会进循环，最终会一直加到 sum 与 $-3$ 奇偶匹配的某个大值，返回一个远大于 $2$ 的错误答案。

错误写法：循环条件只判 sum < target，漏掉奇偶性 → 用例 target = 2 → k = 2 时 sum = 3 >= 2 立刻退出返回 $2$，但两步只能到达 $\pm 1, \pm 3$，到不了 $2$，正确答案是 $3$。

错误写法：循环条件只判奇偶性，漏掉 sum < target → 用例 target = 4 → k = 0 时 sum = 0，(0 - 4) % 2 == 0 成立，条件不满足直接退出返回 $0$，但一步没走怎么可能到 $4$。

错误写法：把奇偶判断写成 (sum - target) % 2 == 1 → 用例 target = 2 → k = 0 时 sum - target = -2，k = 1 时为 $-1$，Java 中 -1 % 2 等于 $-1$ 而非 $1$，条件为假；此时若 sum < target 那一半也恰好为假就会提前退出，返回错误的小值。

错误写法：循环体写成先 sum += k 再 k++ → 用例 target = 1 → 第一轮 sum += 0 后 k 变 $1$，sum 始终比正确值少一次累加，sum 永远追不上正确的 $S_k$，返回值偏大。

错误写法：认为「先走到刚好超过 target 就停」是答案 → 用例 target = 5 → $S_3 = 6 \ge 5$ 就返回 $3$，但 $6 - 5 = 1$ 是奇数，三步到不了 $5$；正确答案是 $5$（$S_5 = 15$，差 $10$ 是偶数）。

错误写法：用 Math.abs(sum - target) % 2 之外还额外判断 sum == target 时提前返回 → 用例 target = 3 → k = 2 时 sum == 3 直接返回 $2$，本例恰好正确，但把这个提前返回写在循环体开头（k 自增之前）就会在 target 为 $0$ 之类的输入上返回 $0$，与题目「target != 0」的假设脱节且掩盖了统一判定的简洁性。

错误写法：用二分查找 $k$ 但只对「$S_k \ge target$」做单调判定 → 用例 target = 2 → 二分找到的是 $k = 2$（最小满足 $S_k \ge 2$ 的值），但它奇偶不匹配；奇偶条件对 $k$ 不单调，不能直接二分，必须在二分结果上再向上线性微调最多 $3$ 步。

错误写法：用公式 k = ceil((-1 + sqrt(1 + 8*target)) / 2) 直接算下界却不做微调 → 用例 target = 2 → 算出 $k = 2$ 后直接返回，漏掉奇偶修正，答案错误；即便加了修正，浮点开方在 $target$ 接近 $10^9$ 时可能因精度误差算出相邻的错误整数。

错误写法：用 long 存 sum 却用 int 存 target 并在比较时发生隐式提升的误判，或反过来把 sum 声明成 short / int16 → 用例 target = 10^9 → sum 需要到约 $10^9$，窄类型直接溢出成负数，循环条件永远成立，死循环。

相似题目

题目	难度	考察点
991. 坏了的计算器	中等	同为「操作固定、求最少次数」，但要反向从目标倒推并用贪心而非奇偶判定
397. 整数替换	中等	也靠奇偶性决定下一步走法，但需要在两种选择间做局部最优判断
279. 完全平方数	中等	同样把目标拆成一组特定数之和，但项可重复使用，要用动态规划而非闭式判定
343. 整数拆分	中等	拆分求乘积最大，考察数学结论（尽量拆成 $3$）与动态规划的对照
69. x 的平方根	简单	本题若改用公式解 $k$ 就要开方，这题正好练习避开浮点误差的整数二分写法