RangeSumQueryImmutable [source code]
public class RangeSumQueryImmutable {
static
/******************************************************************************/
public class NumArray {
int[] sums;
public NumArray(int[] nums) {
sums = new int[nums.length];
int sum = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
sums[i] = sum;
}
}
public int sumRange(int i, int j) {
if (i < 0 || j < 0 || i >= sums.length || j >= sums.length || i > j) return 0;
if (i == 0) return sums[j];
return sums[j] - sums[i - 1];
}
}
/******************************************************************************/
public static void main(String[] args) {
int[][] inputs = {
{-2, 0, 3, -5, 2, -1}, {0, 2, 1}, {2, 5, -1}, {0, 5, -3},
{-4, -5}, {0,0,-4}, {1,1,-5}, {0,1,-9},
};
for (int i = 0; i < inputs.length / 4; i++) {
System.out.println(Printer.seperator());
int[] nums = inputs[4 * i];
RangeSumQueryImmutable.NumArray tester = new RangeSumQueryImmutable.NumArray(nums);
Printer.openColor("magenta");
System.out.println(Printer.array(nums));
for (int j = 1; j < 4; j++) {
int[] call = inputs[j + 4 * i];
int n1 = call[0], n2 = call[1], expected = call[2];
int output = tester.sumRange(n1, n2);
Printer.closeColor();
System.out.printf("sumRange(%d, %d) = %d, ", n1, n2, output);
Printer.openColor(output == expected ? "green" : "red");
System.out.println("expected: " + expected);
Printer.closeColor();
}
}
}
}
"many calls"类的优化, 好像能想到的也只有cache了?
这个题目比较脏的, 最后一个case特别大, 如果不加优化, 就超时, 但是我一开始的做法是用一个[i][j]的数组来cache, 但是这个直接就memory limit exceeded了; 看来要改想法了.
问题想的简单一些, 这个问题不是真的让你实现一个无所不能的array, 而是只要能够提供快速的rangeSum查询这个API就行了;
这个问题的query optimization并不能通过简单的cache完成. 这里给出这个many calls的提示, 其实是希望你在实现的时候要小心选择你的实现的思路, 因为这个问题本身看起来是一个很简单的问题, 所以实现的思路就很多;
这个题目最后的思路属于什么呢? 可以认为是降低了整体算法的普适性. 当然, 无论是cache, 还是这个问题最终的优化, 其实你要完成的都是一个change how you store your data, change the choice of data structures. 当然, 这个只是一个大命题, 真正还要具体问题来分析;
这里的这个优化其实也可以理解为类似DP里面的memoization.
速度是207ms (88%), good enough;
这个是editorial里面的实现方式:
private int[] sum;
public NumArray(int[] nums) {
sum = new int[nums.length + 1];
for (int i = 0; i < nums.length; i++) {
sum[i + 1] = sum[i] + nums[i];
}
}
public int sumRange(int i, int j) {
return sum[j + 1] - sum[i];
}
注意他这里的array的长度的选择;
discussion里面基本也就是这个思路了, 这个题目也就这么点别别窍了;
Problem Description
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.
Difficulty:Easy
Total Accepted:70.5K
Total Submissions:242.5K
Contributor: LeetCode
Companies
palantir
Related Topics
dynamic programming
Similar Questions
Range Sum Query 2D - Immutable Range Sum Query - Mutable Maximum Size Subarray Sum Equals k
/**
- Your NumArray object will be instantiated and called as such:
- NumArray obj = new NumArray(nums);
- int param_1 = obj.sumRange(i,j);
*/