303. Range Sum Query - Immutable

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

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

}