LeetCode Range Sum Query - Immutable

1621 단어
원제는 다음과 같습니다.https://leetcode.com/problems/range-sum-query-immutable/
이 함수는 여러 번 호출되기 때문에 매번 한 번 계산하는 데 많은 시간이 걸린다.
그래서 과거의 값을 dp수 그룹으로 저장합니다.dp[i]는nums[0]에서nums[i-1]까지의 합을 나타낸다. 이렇게 하는 것은sumRange를 구할 때 i==0을 추가로 토론할 필요가 없는 경우이다.
AC Java:
 1 public class NumArray {
 2     private int [] dp;
 3     public NumArray(int[] nums) {
 4         dp = new int[nums.length+1]; //dp[i]   nums[0] nums[i-1]  
 5         for(int i = 1; i<=nums.length; i++){
 6             dp[i] = dp[i-1] + nums[i-1];
 7         }
 8     }
 9 
10     public int sumRange(int i, int j) {
11         return dp[j+1] - dp[i];
12     }
13 }
14 
15 // Your NumArray object will be instantiated and called as such:
16 // NumArray numArray = new NumArray(nums);
17 // numArray.sumRange(0, 1);
18 // numArray.sumRange(1, 2);

좋은 웹페이지 즐겨찾기