[Leetcode]303. Range Sum Query - Immutable
题目简单。最开始一个一个加起来的,还感觉这简直太简单了。后来果然不出所料,超时了。。。然后被逼无奈,打算建一个一维数组,前面所有数字的和。
可以用两种方法做的dp。
可以用两种方法做的dp。
public class NumArray { int[] n; int l; public NumArray(int[] nums) { this.n = new int[l]; this.n = nums; int l = nums.length; if(nums != null && l > 0){ n[0] = nums[0]; for(int i=1; i<l; i++){ n[i] = n[i-1] + nums[i]; } } } public int sumRange(int i, int j) { return i==0 ? n[j] : n[j] - n[i-1]; } }
思路一样,但是下面这个别人的比我的快,代码也好看一些似乎。
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]; } }
Comments
Post a Comment