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:
给定一个int数组，返回i和j之间的元素总和，注意时间复杂度
思路：dp问题， sums[i]表示0到i之间数据的总和，这样sums[j]-sums[i]就是i到j之间的总和
1 class NumArray { 2 3 int[] sums; 4 public NumArray(int[] nums) { 5 sums = new int[nums.length]; 6 if (nums.length == 0) return; 7 sums[0] = nums[0]; 8 for (int i=1;i<nums.length;i++) 9 { 10 sums[i] = sums[i-1] + nums[i]; 11 } 12 } 13 14 public int sumRange(int i, int j) { 15 return i==0?sums[j]:sums[j]-sums[i-1]; 16 } 17 }
303. Range Sum Query - Immutable
原文：http://www.cnblogs.com/wzj4858/p/7687805.html