303. 区域和检索 - 数组不可变
题目
给定一个整数数组 nums，求出数组从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点。
实现 NumArray 类：
NumArray(int[] nums) 使用数组 nums 初始化对象
int sumRange(int i, int j) 返回数组 nums 从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点（也就是 sum(nums[i], nums[i + 1], ... , nums[j])）
示例：
输入：
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
输出：
[null, 1, -1, -3]
code
class NumArray {
int[] nums;
int[] prefix;
public NumArray(int[] nums) {
this.nums=nums;
prefix=new int[nums.length+1];
prefix(prefix,nums);
}
public int sumRange(int i, int j) {
return prefix[j+1]-prefix[i];
}
public void prefix(int[] prefix,int[] nums){
for(int i=0;i<nums.length;i++){
prefix[i+1]=prefix[i]+nums[i];
}
}
}
/**
* Your NumArray object will be instantiated and called as such:
* NumArray obj = new NumArray(nums);
* int param_1 = obj.sumRange(i,j);
*/
754. 到达终点数字
题目
在一根无限长的数轴上，你站在0的位置。终点在target的位置。
每次你可以选择向左或向右移动。第 n 次移动（从 1 开始），可以走 n 步。
返回到达终点需要的最小移动次数。
示例 1:
输入: target = 3
输出: 2
解释:
第一次移动，从 0 到 1 。
第二次移动，从 1 到 3 。
示例 2:
输入: target = 2
输出: 3
解释:
第一次移动，从 0 到 1 。
第二次移动，从 1 到 -1 。
第三次移动，从 -1 到 2 。
思路
其实相当于给定数字1到k，你可以用加号或者减号，使得1到k的一种组合之和是n。
code
class Solution {
public int reachNumber(int target) {
target=Math.abs(target);
int k=0;
int sum=0;
while(sum<target){
k++;
sum+=k;
}
if(sum==target) return k;
//sum>target
int deta=sum-target;
if(deta%2==0) return k;
if(k%2==0) return k+1;
return k+2;
}
}
