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);
    */

results matching ""

    No results matching ""