Question

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)\mod 2 = 0$，此时的移动次数 $k$ 就是答案，直接返回。

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

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

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

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;
    }
  }
}

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;
    }
  }
};

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
  }
}

/**
 * @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;
  }
};