754. 到达终点数字

English Version

题目描述

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

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

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

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

 

示例 1:

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

示例 2:

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

 

提示:

• -109 <= target <= 109
• target != 0

解法

方法一：数学分析

由于对称性，每次可以选择向左或向右移动，因此，我们可以将 $target$ 统一取绝对值。

定义 $s$ 表示当前所处的位置，用变量 $k$ 记录移动的次数。初始时 $s$ 和 $k$ 均为 $0$。

我们将 $s$ 一直循环累加，直到满足 $s\ge target$ 并且 $(s-target)\mathrm{mod}2=0$，此时的移动次数 $k$ 就是答案，直接返回。

为什么？因为如果 $s\ge target$ 且 $(s-target)\mathrm{mod}2=0$，我们只需要把前面 $\frac{s-target}{2}$ 这个正整数变为负数，就能使得 $s$ 与 $target$ 相等。正整数变负数的过程，实际上是将移动的方向改变，但实际移动次数仍然不变。

时间复杂度 $O(\sqrt{\left|target\right|})$，空间复杂度 $O(1)$。

Python3

class Solution:
    def reachNumber(self, target: int) -> int:
        target = abs(target)
        s = k = 0
        while 1:
            if s >= target and (s - target) % 2 == 0:
                return k
            k += 1
            s += k

Java

class Solution {
    public int reachNumber(int target) {
        target = Math.abs(target);
        int s = 0, k = 0;
        while (true) {
            if (s >= target && (s - target) % 2 == 0) {
                return k;
            }
            ++k;
            s += k;
        }
    }
}

C++

class Solution {
public:
    int reachNumber(int target) {
        target = abs(target);
        int s = 0, k = 0;
        while (1) {
            if (s >= target && (s - target) % 2 == 0) return k;
            ++k;
            s += k;
        }
    }
};

Go

func reachNumber(target int) int {
	if target < 0 {
		target = -target
	}
	var s, k int
	for {
		if s >= target && (s-target)%2 == 0 {
			return k
		}
		k++
		s += k
	}
}

JavaScript

/**
 * @param {number} target
 * @return {number}
 */
var reachNumber = function (target) {
    target = Math.abs(target);
    let [s, k] = [0, 0];
    while (1) {
        if (s >= target && (s - target) % 2 == 0) {
            return k;
        }
        ++k;
        s += k;
    }
};

...