在一根无限长的数轴上,你站在0的位置.终点在target的位置.
每次你可以选择向左或向右移动.第 n 次移动(从 1 开始),可以走 n 步.
target是在[-10^9 10^9]范围中的非零整数.
不难看出, 问题的本质就是一个有限序列, 1,2,3,4... .我们的目标是给这个序列的元素添加正负号,是的其和为 target.这和 494.target-sum 的思路是一样的.
为什么是有限序列?
因为我们始终可以在 target 次以内走到 target.严格来说, 最少在根号 target 左右就可以走到 target.
和 494.target-sum 不同的是, 这道题数组是无限的,看起来似乎更难,实际上更简单, 因为数组是有规律的,每次都递增 1.
由于 target 正负是对称的, 因此 target 最少走多少布,-target 也是多少步.因此我们只考虑一种情况即可, 不妨只考虑正数的情况.