LeetcodeRangeSumQueryImmutable

Givenanintegerarraynums,findthesumoftheelementsbetweenindicesiandj(i≤j),inclusive.Example:

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.

---

解题思路：

最简单的dynamic Programming.  Complexity: NumArray O(n)   sumRange O(1)

为了解决边界问题， 建立accu = new int[nums.length+1]   accu[i]表示nums[0]+...+ nums[i-1]

recurrence formula：accu[i] = accu[i-1] + nums[i-1]     base case: accu[0]= 0

---

Java code:

public class NumArray { private int[] accu; public NumArray(int[] nums) { accu = new int[nums.length+1]; accu[0] = 0; for(int i = 1; i<= nums.length; i++){ accu[i] = accu[i-1] + nums[i-1]; } } public int sumRange(int i, int j) { return accu[j+1] - accu[i]; }}// Your NumArray object will be instantiated and called as such:// NumArray numArray = new NumArray(nums);// numArray.sumRange(0, 1);// numArray.sumRange(1, 2);

---

Reference:

1. https://leetcode.com/discuss/68725/5-lines-c-4-lines-python

2. https://leetcode.com/discuss/69081/3ms-java-solution-with-array-no-special-i-0-check

Leetcode Range Sum Query - Immutable