754. Reach a Number

754. 到达终点数字

在一根无限长的数轴上，你站在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]范围中的非零整数。

解法一

//时间复杂度O(1), 空间复杂度O(1)
class Solution {
public:int reachNumber(int target) {int n = ceil( (sqrt(1 + 8.0 * abs(target)) - 1 ) / 2);int sum = n * (n + 1) / 2;int diff = sum - target;if(diff % 2 == 0) return n;if(n % 2 == 0) return n + 1;return n + 2;}
};

思路：

这个题标签是简单难度，但是如果第一次做只凭自己想还是很难做出来的，需要发现一些隐含的规律。

此题换一种表达，大概如下：

对于一个n个元素的序列 ±1, ±2, ±3, ±4, ..., ±n. ±号意思是每个元素均可取正或取负。现在给定一个非负整数target，求n的最小值，使这个序列的和刚好为target。

代码的计算步骤如下：

1. 从n = +1开始累加，直到累加和sum >= target；这一步的n及sum可以直接解二次方程计算出来：

int n = ceil( (sqrt(1 + 8.0 * abs(target)) - 1 ) / 2);
int sum = n * (n + 1) / 2;

ceil是向上取整；对target取绝对值，因为对称性，target正负不影响计算结果，统一当成正整数。 2. 然后计算累计和sum与目标target的差：

    int diff = sum - target;

1. 接下来要分情况了。
2. 第一种情况：diff = 0。理想情况，此时说明累加n步刚好到达target，此时返回n即可；
3. 第二种情况：diff为偶数。此时的累计和sum虽然比target大，但是可以将序列中的第 diff / 2 个元素的正号改为负号，此时其和就是target。这种情况同样返回n即可。
4. 第三种情况：diff为奇数 且 n 为偶数。此时只需要将sum再加上一个 n + 1，就可以凑成第二种情况的条件（diff为偶数）。此时返回 n + 1 就是答案。
5. 第四种情况：diff为奇数 且 n 为奇数。此时需要将sum加上一个 n + 1 及 n + 2 才可凑成第二种情况。这样返回 n + 2 就是答案。
6. 第一种情况可以与第二种情况合并，体现到代码上就是：

    //求出n和sum, 使sum >= target且n最小int n = ceil( (sqrt(1 + 8.0 * abs(target)) - 1 ) / 2);int sum = n * (n + 1) / 2;//求出和与目标数的差diffint diff = sum - target;//如果差为偶数, 直接返回nif(diff % 2 == 0) return n;//如果差为奇数, 且n为偶数, 返回n + 1if(n % 2 == 0) return n + 1;//如果差为奇数, 且n为奇数, 返回n + 2return n + 2;