LeetCode中怎么实现区域和检索-内江站浩晨众云

新闻中心

这里有您想知道的互联网营销解决方案

LeetCode中怎么实现区域和检索

本篇文章为大家展示了LeetCode中怎么实现区域和检索，内容简明扼要并且容易理解，绝对能使你眼前一亮，通过这篇文章的详细介绍希望你能有所收获。

创新互联公司坚持“要么做到，要么别承诺”的工作理念，服务领域包括：成都网站建设、网站设计、企业官网、英文网站、手机端网站、网站推广等服务，满足客户于互联网时代的桂平网站设计、移动媒体设计的需求，帮助企业找到有效的互联网解决方案。努力成为您成熟可靠的网络建设合作伙伴！

给定一个整数数组 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)

上述内容就是LeetCode中怎么实现区域和检索，你们学到知识或技能了吗？如果还想学到更多技能或者丰富自己的知识储备，欢迎关注创新互联行业资讯频道。

当前标题：LeetCode中怎么实现区域和检索
新闻来源：http://www.jxjierui.cn/article/gggese.html

新闻中心

其他资讯