Medium

题目描述

你站在位置 0 的无限数轴上。有一个目标位置 target。

你可以进行若干次移动 numMoves：

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

给定整数 target，返回到达目标位置所需的最少移动次数（即最小 numMoves）。

示例 1：

输入: target = 2
输出: 3
解释:
第1次移动，从0到1（1步）。
第2次移动，从1到-1（2步）。
第3次移动，从-1到2（3步）。

示例 2：

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

约束条件：

  • -10^9 <= target <= 10^9
  • target != 0

解题思路

解题思路

这道题的关键在于理解移动的规律和数学性质。

首先，由于数轴是对称的，我们可以只考虑正数情况，最后的结果对于负数是相同的。

核心思路是：

  1. 我们总是先尽可能向右走，直到走过目标位置
  2. 如果恰好到达目标，那就是答案
  3. 如果超过了目标，我们需要通过改变某些步骤的方向来调整

具体分析：

  • 经过 n 步后，如果所有步骤都向右走，我们会到达位置 sum = 1 + 2 + ... + n = n*(n+1)/2
  • 如果 sum >= target 且 (sum - target) 是偶数，那么我们可以通过改变某些步骤的方向来恰好到达 target
  • 为什么要求差值是偶数？因为如果我们把第 k 步从向右改为向左，总位置会减少 2k，所以差值必须是偶数才能被完全抵消

算法步骤：

  1. 取 target 的绝对值
  2. 找到最小的 n 使得 n*(n+1)/2 >= target
  3. 如果 (sum - target) 是偶数，返回 n
  4. 否则继续增加 n，直到差值为偶数

代码实现

class Solution {
public:
    int reachNumber(int target) {
        target = abs(target);
        int n = 0;
        int sum = 0;
        
        while (sum < target) {
            n++;
            sum += n;
        }
        
        while ((sum - target) % 2 != 0) {
            n++;
            sum += n;
        }
        
        return n;
    }
};

class Solution:
    def reachNumber(self, target: int) -> int:
        target = abs(target)
        n = 0
        sum_val = 0
        
        while sum_val < target:
            n += 1
            sum_val += n
        
        while (sum_val - target) % 2 != 0:
            n += 1
            sum_val += n
        
        return n

public class Solution {
    public int ReachNumber(int target) {
        target = Math.Abs(target);
        int n = 0;
        int sum = 0;
        
        while (sum < target) {
            n++;
            sum += n;
        }
        
        while ((sum - target) % 2 != 0) {
            n++;
            sum += n;
        }
        
        return n;
    }
}

var reachNumber = function(target) {
    target = Math.abs(target);
    let n = 0;
    let sum = 0;
    
    while (sum < target) {
        n++;
        sum += n;
    }
    
    while ((sum - target) % 2 !== 0) {
        n++;
        sum += n;
    }
    
    return n;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(√target)主要是找到合适的 n 值，n 大约是 √(2*target)
空间复杂度O(1)只使用常数级额外空间

相关题目