303. Range Sum Query - Immutable

发表于 | 分类于

题目描述

给定一个数组，求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和，包含 i, j 两点。

例如：

给定nums = [-2, 0, 3, -5, 2, -1]，求和函数为sumRange()

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

注意:

  1. 你可以假设数组不可变。
  2. 会多次调用 sumRange 方法。

我的解法——DP（最优，AC）

  • 当前状态可能由前一个状态转移得来：DP[i]=DP[i - 1] + nums[i]
  • 复杂度O(n)
  • 结果：Beat 52.24%
class NumArray:

    def __init__(self, nums):
        """
        :type nums: List[int]
        """
        length = len(nums)
        self.dp = [-1] * length
        if(length != 0):
            self.dp[0] = nums[0]
        for i in range(1,length):
            self.dp[i] = nums[i] + self.dp[i - 1]
        
    def sumRange(self, i, j):
        """
        :type i: int
        :type j: int
        :rtype: int
        """
        if(i == 0):
            return self.dp[j]
        else:
            return self.dp[j] - self.dp[i - 1]


# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# param_1 = obj.sumRange(i,j)

其他解法——记忆搜索

  • 预先计算所有范围和的可能性并将其结果存储在散列表中，我们可以加快查询的速度。
  • 时间O(n2)，空间O(n2)。
private Map<Pair<Integer, Integer>, Integer> map = new HashMap<>();

public NumArray(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        int sum = 0;
        for (int j = i; j < nums.length; j++) {
            sum += nums[j];
            map.put(Pair.create(i, j), sum);
        }
    }
}

public int sumRange(int i, int j) {
    return map.get(Pair.create(i, j));
}

参考答案

  • https://leetcode.com/problems/range-sum-query-immutable/solution/