[LeetCode]Dp303 区域检索 [前缀和 ]

传送门：https://leetcode-cn.com/problems/range-sum-query-immutable/

题目

给定一个整数数组 nums，求出数组从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j两点。

示例：

输入： [“NumArray”, “sumRange”, “sumRange”, “sumRange”] [[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]] 输出： [null, 1, -1, -3]

解释： NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]); numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3) numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1)) numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))

BF检索可以做，但是会超时

解题思路：动态规划

假设数组 _nums_ 的长度为 n，创建长度为 n+1 的前缀和数组 dp

对于 都有
当 时， 表示数组 从下标 到下标 的前缀和。

将前缀和数组 的长度设为 n+1 的目的是为了方便计算 sumRange(i,j)，不需要对i=0 的情况特殊处理。此时有：

代码

官方代码 [ 简洁 ]

（ dp[i]表示从下标 0 到下标 i-1 的前缀和）

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

我的代码

（ dp[i]表示从下标 0 到下标 i 的前缀和）

public class Demo {
    int[]dp;
    int[] nums;
    //dp[i]为[0...i]的和
    public Demo(int[] nums) {
        this.nums=nums;
        dp=new int[nums.length];
        dp[0]=nums[0];
        for (int i = 1; i < nums.length;i++) {
            dp[i]=dp[i-1]+nums[i];
        }
    }

    public int sumRange(int left, int right) {
        return dp[right]-dp[left]+nums[left];
    }
}