力扣(LeetCode)754. 到达终点数字(C++)

数学分析

分类讨论:

1. 沿着一个方向，当走了i步，刚好走到 $target$ ， $returni$ ;
2. 沿着一个方向，当走了i步，越过 $target$ 偶数步，只需要反转之前的某一步，即可走到终点。
3. 沿着一个方向，当走了 $i$ 步，越过 $target$ 奇数步，再走一步，越过 $target$ 偶数步，转换为 $2.$
4. 沿着一个方向，当走了 $i$ 步，越过 $target$ 奇数步，再走两步，越过 $target$ 偶数步，转换为 $2.$

数学推理请看链接，灵茶山艾府-分类讨论+详细证明+简洁写法+优化（Python/Java/C++/Go）

代码展示

class Solution {
public:
    int reachNumber(int target) {
        //第i次移动走i个数字
        //target !=0
        //越过target，当sum{k},{1} - target为偶数，反转某一步，即可得到答案。
        target = abs(target);
        int ans = 1,step =0;//答案ans，总步长step
        while(step<target||(step-target)%2) step+=ans++;
        return ans-1;//step += ans,然后ans++,所以step满足退出条件时，ans多++了一次。return ans-1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

博主致语

理解思路很重要！
欢迎读者在评论区留言，作为日更博主，看到就会回复的。

AC

复杂度分析

1. 时间复杂度:$O(\sqrt{|target|})$，甚至有O(1)的做法，看链接里的证明和公式，这里的$O(\sqrt{|target|})$根据公式得来。
2. 空间复杂度:$O(1)$。