到达终点数字【LC754】

You are standing at position 0 on an infinite number line. There is a destination at position target.

You can make some number of moves numMoves so that:

• On each move, you can either go left or right.
• During the ith move (starting from i == 1 to i == numMoves), you take i steps in the chosen direction.

Given the integer target, return the minimum number of moves required (i.e., the minimum numMoves) to reach the destination.

在一根无限长的数轴上，你站在0的位置。终点在target的位置。

你可以做一些数量的移动 numMoves :

• 每次你可以选择向左或向右移动。
• 第 i 次移动（从 i == 1 开始，到 i == numMoves ），在选择的方向上走 i 步。

给定整数 target ，返回 到达目标所需的 最小 移动次数(即最小 numMoves ) 。

还好dp、递归写不出来，就直接看题解了，这不是我能想到的方法

• 思路

1.数轴上的任意点都以起点（0 点）对称，只需要考虑对称点的任意一边

左边所能到达任意一个点，都能通过调整所达路径的方向来将终点调整到右边。

2.先往靠近 target 的方向移动，到达或越过 target 的时候则停止

。若能直接到达 target，此时消耗的必然是最小步数，可直接返回；

。若越过了target，那么需要考虑是否需要增加额外步数到达target

3.我们假设需要调整的步数总和为tot，则有$ dist−2×tot=target，变形可得 ，变形可得，变形可得tot = \frac{dist - target}{2}$

。当tot为整数时，即$ dist−target$为偶数时，不需要引入额外步数，只需要将某些数反向即可

。当tot不为整数时，即$ dist−target$为奇数时，只能引入额外步数，继续往右走，使两者差值为偶数

• 实现

class Solution {
    public int reachNumber(int target) {
        while (target < 0){
            target = -target;
        }
        int dis = 0;
        int i = 1;
        while (dis < target || (dis > target && (dis - target) % 2 == 1 ) ){
            dis += i;
            i++;
        }       
        return i - 1;
    }
}

• 复杂度

。时间复杂度：O ( n )

。空间复杂度：O ( 1 )

• 代码优化：利用等差数列的性质，找到第一个S _k > = t a r g e t

。等差数列前n项和计算公式

。当a ₀ = 0 、 a ₁ = 1 、当前步数为k、d=1时，

。首先找到第一个S _k > = t a r g e t ，k = s q r t ( 2 ∗ t a r g e t ) ，此时移动的距离为S _k

。代码

只需判断是否需要进行额外移动，额外移动最多4次

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

。复杂度

• 时间复杂度：O ( 1 )

• 空间复杂度：O ( 1 )