/*
*
303. Range Sum Query - Immutable
Total Accepted: 34053 Total Submissions: 135853 Difficulty: Easy
Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.
Example:
Given nums = [-2, 0, 3, -5, 2, -1]
sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3
Note:
You may assume that the array does not change.
There are many calls to sumRange function.
Hide Company Tags Palantir
Hide Tags Dynamic Programming
Show Similar Problems
*/
package dp;
import java.util.Arrays;
public class RangeSumQuery {
private int[] sums;
// private int[] array;
public RangeSumQuery(int[] nums) {
// array = Arrays.copyOf(nums, nums.length); // 不需要了
for (int i = 1; i < nums.length; i++) {
nums[i] += nums[i - 1];
// System.out.printf("nums[%d] = %d \n", i, nums[i]);
}
sums = nums;
}
public int sumRange(int i, int j) {
if (i == 0) {
return sums[j];
}
return sums[j] - sums[i - 1];
// return dp[j] - dp[i] + array[i]; ==> dp[j] - dp[i - 1] 避免了增加array数组
}
public static void main(String[] args) {
int[] nums = {-2, 0, 3, -5, 2, -1};
RangeSumQuery rsq = new RangeSumQuery(nums);
System.out.println(rsq.sumRange(0, 2) == 1);
System.out.println(rsq.sumRange(0, 2));
System.out.println(rsq.sumRange(2, 5) == -1);
System.out.println(rsq.sumRange(2, 5));
System.out.println(rsq.sumRange(0, 5) == -3);
System.out.println(rsq.sumRange(0, 5));
}
}
303. Range Sum Query - Immutable
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- Given an integer array nums, find the sum of the elements...
- Given an integer array nums, find the sum of the elements...
- 1.描述 Given an integer array nums, find the sum of the ele...
- Q: Given an integer array nums, find the sum of the eleme...
