leetcode.754 到达终点数字 - 数学思维

754. 到达终点数字

从1到n一直累加, 直到sum==target, 或sum-target为偶数.

因为在第n步往回走一次,sum就会减少2n, 所以他们的差必须是偶数才能到.

本来想用前缀和+找规律 但是后面发现是数学问题……好难QAQ

第一点：target正负情况是一样的，所以统一把target转化为正数

• 我们的策略就是一直向右走，直到走到的位置超过target，此时的idx=1+2+……+k>=target
• 此时超出的距离为over = idx - target
• 所以我们将之前走过的某一步x反向，使idx' = 1+2+……-x+……+k = target = idx - over
• 某一步反向也就是在idx基础上-2x，即idx' = idx-2x（因为idx是+x，而idx'是-x，两者相差2x）
• 所以over = 2x = idx - target，所以idx - target必须是偶数
• 所以我们只需要找到第一个使 idx = 1 + 2 + ... + k >= target 且 idx - target 为偶数的 k 即为答案

class Solution {
    public int reachNumber(int target) {
 
        target=Math.abs(target);
        int cnt=0,idx=0;
        while(idx2==1) //idx
            idx+=++cnt;
        return cnt;
    }
}