LeetCode刷题DAY 32：区域和检索 - 数组不可变

三猫

发布于 2020-06-21 16:16:14

2920

发布于 2020-06-21 16:16:14

文章被收录于专栏：机器学习养成记

难度：简单关键词：缓存、动态规划

⭐️⭐️

题目描述

给定一个整数数组 nums，建立一个函数用于求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和，包含 i, j 两点。如：输入nums = [-2, 0, 3, -5, 2, -1]，sumRange(0, 2) =1。

题解

思路：动态规划、缓存

本题可以直接用sum函数，但是耗时较长。中间状态dp[i]表示从0-i的和，则要求i-j的和等于dp[j]-dp[i-1]，因此首先建立一个数组记录dp，然后根据想要求的范围进行计算。此处要注意的是，当i=0时，dp[j]-dp[i-1]会溢出，所以dp的长度是len(nums)+1，第一个元素为0表示i=0之前没有值。

class NumArray:

    def __init__(self, nums: List[int]):
        if len(nums)==0:
            return
        self.dp = [0]*(len(nums)+1)
        self.dp[1]=nums[0]
        for i in range(2,len(nums)+1):
            self.dp[i] = self.dp[i-1]+nums[i-1]

    def sumRange(self, i: int, j: int) -> int:
        return self.dp[j+1]-self.dp[i]

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

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-06-18，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法