leetcode 303. Range Sum Query - Immutable

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.

暴力解法要有两层循环，造成复杂度为 O(N2) ，造成这样的主要原因是重复计算，部分的计算结果没有保留。 记 s(i,j) 为要求的值，不难发现 s(i,j)=s(0,j)−s(0,i−1) ，这样的话我们只需要保存一个长度为n的数值，保存 s(0,i) 的值即可。

public class NumArray { int[] partSum; public NumArray(int[] nums) { if(nums!=null && nums.length >= 1){ int len = nums.length; partSum = new int[len]; partSum[0] = nums[0]; for(int i=1; i<len; i++){ partSum[i] = partSum[i-1] + nums[i]; } } } public int sumRange(int i, int j) { if(partSum==null || partSum.length==0) return 0; if(i==0) return partSum[j]; return partSum[j] - partSum[i-1]; } }

Top的的写法

public class NumArray { private int[] sums; public NumArray(int[] nums) { if(nums.length != 0){ sums = new int[nums.length]; sums[0] = nums[0]; for(int i=1; i<nums.length; i++){ sums[i] = nums[i] + sums[i-1]; } } } public int sumRange(int i, int j) { return i==0 ? sums[j] : sums[j]-sums[i-1]; } }