难度: Medium
在一根无限长的数轴上，你站在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 <= 109target != 0运行时间: 26 ms
内存: 16.0 MB
class Solution:
def reachNumber(self, target: int) -> int:
target =abs(target)
l = 0
r = target+1
while l + 1 < r:
mid = (l +r)//2
s = (mid +1)*mid//2
if s <target:
l =mid
else:
r =mid
sm = (1 + r)*r//2
if sm == target or (sm- target)%2==0:
return r
else:
return r + 1 + r % 2
这个题解使用了二分查找的方法来寻找最小的移动次数。首先，将目标值 target 取绝对值，因为向左和向右移动是对称的，所以只需要考虑非负的情况。接着使用二分查找来寻找一个数 r，使得从 1 到 r 的和大于等于 target。这个和可以用公式 (1 + r) * r // 2 来计算。最后，检查从 1 到 r 的和是否与 target 相等，或者它们的差是偶数。如果是，那么 r 就是答案。如果不是，那么需要额外的一步或两步来达到 target，具体取决于 r 是奇数还是偶数。
时间复杂度: O(log(target))
空间复杂度: O(1)
class Solution:
def reachNumber(self, target: int) -> int:
target = abs(target) # 取绝对值
l = 0
r = target + 1
while l + 1 < r: # 二分查找
mid = (l + r) // 2
s = (mid + 1) * mid // 2 # 计算从1到mid的和
if s < target:
l = mid
else:
r = mid
sm = (1 + r) * r // 2 # 计算从1到r的和
if sm == target or (sm - target) % 2 == 0: # 检查是否能够达到target
return r
else:
return r + 1 + r % 2 # 需要额外的步骤来调整最后的位置
在这个问题中，无论是向左还是向右移动，都可以看作是向目标值的正或负方向逼近。因此，目标值的正负并不影响最终需要的步数，只是方向不同。将`target`取绝对值是为了简化问题，只考虑从0到正数的情况，这样做可以不用分别处理正负两种情况，从而简化代码和逻辑。
设置初始右边界`r`为`target + 1`是基于从1到`r`的和至少需要达到`target`的考量。由于数列1到`r`的和是递增的，`target + 1`确保在最坏情况下，即`target`正好是从1到`r`的和时，二分查找不会错过可能的正确答案。在实际应用中，这个设置通常是足够的，因为它保证了右边界初始时一定大于或等于所需的最小`r`值。
公式`(mid + 1) * mid // 2`是等差数列求和公式的应用，计算的是从1到`mid`的整数和。这里`+1`是因为等差数列的公式通常形式为`(首项 + 末项) * 项数 / 2`，在这里首项是1，末项是`mid`，项数是`mid`。因此，`(mid + 1)`是首项加末项，`mid`是项数，整个公式计算的是1到`mid`的整数和。
当`(sm - target) % 2 == 0`时，表示从1到`r`的和与目标值`target`之间的差可以通过改变某些步骤的方向（即将部分正向步骤改为负向）来精确抵消。这是因为每次改变一个数的方向，等于在总和中减去这个数的两倍。只有当这个差是偶数时，才可能通过整数次的方向改变达到目标。如果差是奇数，无法通过简单的方向改变达到平衡，此时需要考虑`r`的奇偶性。如果`r`是奇数，再加一步可以使得总和变化的差也是偶数，从而可能通过方向改变满足条件；如果是偶数，可能需要更多步骤调整。