到达终点数字

题目：

你从数轴上的0出发，可以选择向右或向左走，但是第n步只能走n步。问：走到target点所需的最少步数？

 

示例1:

target=2，最少步数为3

解释：向右走1步，向左走2步，向右走3步

 

示例2:

target=4，最少步数为3

解释：向左走1步，向右走2步，向右走3步

 

思路详解：

这道题的本质是 1+2+3+…+n，在一些数字前面取负号（代表向左走），使得这些数字的和等于target。

假设 ，假设在第i个数前面取负号，那么得到的新的和为 sum-2i，变化肯定为偶数！

所以做法就是：一直累加1+2+3+……，直到sum>=target并且sum-target为偶数的时候，一共加了多少个数字，最少步数就为多少！

比如：target=4

要满足sum>=target并且sum-target为偶数，sum = 1+2+3，要使sum=target，只需要1前取负就行：sum=-1+2+3=4！

再比如：target=5

要满足sum>=target并且sum-target为偶数，sum = 1+2+3+4+5，要使sum=target，只需2、3取负：sum=1-2-3+4+5！

在特定数字前面取负，可以形成不大于target本身的所有偶数，所以只要sum-target是偶数，就一定能够使sum=target！

 

完整代码(Java):

public class Solution {
	
	public int MinStep(int target) {
		int sum = 0, i = 0;
		while(true){
			i += 1;
			sum += i;
			if(sum >= Math.abs(target) && (sum-target)%2 == 0) break;
		}
		return i;
	}

}

理解了思路，代码就相当简洁了！

注：要对target取绝对值的原因是防止target为负的情况！