LeetCode刷题【754】到达终点数字

输入: target = 2
输出: 3
解释:
第一次移动，从 0 到 1 。
第二次移动，从 1 到 -1 。
第三次移动，从 -1 到 2 。

输入: target = 3
输出: 2
解释:
第一次移动，从 0 到 1 。
第二次移动，从 1 到 3 。

数学分析计算

如图

1. 假设从左往右走了k次到达M点刚好越过或者达到target点，即k(k+1)/2 ≥ target
2. 那么我们即需要再这之前往反方向移动距离为D
3. 又，因为反向移动了，仍需掉头继续往这个方向移动，即假设我们往反向移动了的距离为x
4. 那么我们就有了2x = D这样的结果，即反向移动加折回到原点0的距离就是我们原先应当到达M点，因为折返损耗了距离D而只能达到位置target的情况
5. 即有，x = D/2，那么我们知道D必然需要为一个偶数，因为x必然是一个整数

举个简单的例子
target = 8
那么我们知道 k = 4 的时候，能到达M点位置为10，测试相差距离D为2，即需要往反向移动x = D/2 = 1距离，那么我们就知道应当按照- 1 + 2 + 3 + 4 = 8的方法运行

代码

class Solution {
    public int reachNumber(int target) {
        if (target==0)return 0;
        target = Math.abs(target);
        int k = (int) Math.sqrt(2 * target);
        k--;
        while ((1 + ++k) * k / 2 < target){}
        int d = (1 + k) * k / 2 - target;
        while (d%2!=0) {
            d += ++k;
        }
        return k;
    }
}