# 0754. 到达终点数字

## 题目地址(754. 到达终点数字)

<https://leetcode-cn.com/problems/reach-a-number/>

## 题目描述

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

每次你可以选择向左或向右移动。第 n 次移动（从 1 开始），可以走 n 步。

返回到达终点需要的最小移动次数。

示例 1:

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

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

target是在[-10^9, 10^9]范围中的非零整数。
```

## 前置知识

* 数学

## 公司

## 思路

不难看出， 问题的本质就是一个有限序列， 1，2，3，4... 。我们的目标是给这个序列的元素添加正负号，是的其和为 target。这和 494.target-sum 的思路是一样的。

拿题目的 target = 3 来说， 就是 1 + 2 = 3。

拿题目的 target = 2 来说， 就是 1 - 2 + 3 = 2。

为什么是有限序列？

因为我们始终可以在 target 次以内走到 target。严格来说， 最少在根号 target 左右就可以走到 target。

和 494.target-sum 不同的是， 这道题数组是无限的，看起来似乎更难，实际上更简单， 因为数组是有规律的，每次都递增 1。

> 由于 target 正负是对称的， 因此 target 最少走多少布，-target 也是多少步。因此我们只考虑一种情况即可， 不妨只考虑正数的情况。

其实，只要找出第一个满足 1 + 2 + 3 + .... + steps > target 的 steps 即可。

令 1 + 2 + 3 + .... + steps 为 T。接下来，我们来对不同情况进行分析。

* 如果 T 等于 target，那么 steps 就是我们想求的值，直接返回即可。
* 否则，我们尝试从 \[1, steps] 这 steps 个数中找出几个数改成其符号，不难知道找的这几个数的和是 (T - target) / 2。
  1. 如果 T 是偶数， 那么我们总可以找出若干数字使其变为符号，满足 1 + 2 + 3 + .... + steps == target，因此直接返回 steps 即可。
  2. 如果 T 是奇数，(T - target) / 2 是个小数，肯定无法选取的，因此我们还需要在多选数，比如 steps + 1，steps + 2。 由于 T + steps + 1 和 T + steps + 1 + steps + 2 中有且仅有一个是偶数。我们仍然可以套用上面的方法，找出若干数字使其变为负号，满足 1 + 2 + 3 + .... + steps + steps + 1 == target 或者 1 + 2 + 3 + .... + steps + steps + 1 + steps + 2 == target。**也就是说在这种情况下答案就是 steps + 1 或者 steps + 2，具体是哪个取决于 T + steps + 1 是偶数还是 T + steps + 1 + steps + 2 是偶数**

## 关键点解析

* 对元素进行分组，分组的依据是符号， 是`+` 或者 `-`
* 通过数学公式推导可以简化我们的求解过程，这需要一点`数学知识和数学意识`

## 代码(Python)

Python Code:

```python
class Solution(object):
    def reachNumber(self, target):
        target = abs(target)
        steps = 0
        while target > 0:
            steps += 1
            target -= steps
        if target & 1 == 0: return steps
        steps += 1
        if (target - steps) & 1 == 0: return steps
        return steps + 1
```

**复杂度分析**

* 时间复杂度：$O(\sqrt target)$
* 空间复杂度：$O(1)$

## 相关题目

* [494.target-sum](https://github.com/azl397985856/leetcode/blob/master/problems/494.target-sum.md)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/754.reach-a-number.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.