题目分析
本题题意非常清晰，就是第i步，可以向左或者向右移动i个单位，问最后到达指定目标最少需要移动的次数。应该如何去求解呢？
数学
其实我一开始想的思路是搜索，但是题目的数据量太大了，如果是1e9的数据量，根据1 + 2 + … + step = 1e9，可以求出step约为1e4以上的量级。那么需要广搜10000步，因此需要2的10000次方的运算量。这是完全不现实的。
有的小伙伴就会提出质疑，是否可以用一个visited哈希表，记录已经遍历过的点呢？这也是不现实的，因为每一个点都会被遍历到，时间复杂度至少是1e9的，此时就不可能通过本题。而且最重要的一点是，当前遍历到x时无法抵达终点，不代表后面再次遍历到x无法抵达终点。这是这个方法无法使用的关键点。如0这个点，一开始就是0，假设无法抵达100，当第100步时，再次到达0，那么是可以抵达100的，如果使用visited哈希表，则认为0这个位置已经遍历过，不去考虑从0直接到100的情况，这是不对的。
所以本题无法使用暴力搜索，只能再想其他的方法。
因为本题是对称的，所以目标为负数的结果和目标为正数的结果相等。为了计算方便，可以先将目标变为正数。
我们可以想到，在一般情况下都会向终点方向移动。是不是可以先尽量向右侧移动。如果超过了目标，则可以将前面的某些步数向左移动呢？
首先找到超过目标的最小步数，根据等差数列求和可知
$$ step = \frac{-1 + \sqrt{1 + 8 \times target}}{2} $$
并且求得经过step步后到达的位置是n = (1 + step) x step
记此时所在位置n和target的差距为diff
下面有三种情况：
- 如果diff为偶数，那么直接将第diff / 2步的右移变为左移即可。这是很好理解的，将某一步x右移变为左移，距离就会减少2x。
- 如果diff为奇数，那么看n是奇数还是偶数，如果n是奇数，那么下一步n + 1一定是偶数，因此多走一步，diff仍然为奇数，所以还需要多走一步。
- 如果diff为奇数，n是偶数，那么下一步n + 1一定是奇数，此时diff是偶数，会变成情况1，因此多走一步即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution {
public int reachNumber(int target) {
target = Math.abs(target);
int step = (int) Math.ceil((-1 + Math.sqrt(8L * target + 1)) / 2);
int diff = (1 + step) * step / 2 - target;
if ((diff & 1) == 0) {
return step;
}
// 下面可以节省为1步，return step + 1 + (step & 1);
if ((step & 1) == 0) {
return step + 1;
} else {
return step + 2;
}
}
}
刷题总结
本题难度不大，但是很难想到，有些贪心的思想，小伙伴们遇到无法搜索的题目，一定要模拟一下，想一想是否可以使用贪心算法求解。