【Leetcode Daily】303区域和检索-数组不可变

发表于2025-06-30|更新于2025-06-30|力扣日常 | LeetcodeDaily

|总字数:309|阅读时长:1分钟|浏览量:

题目浅析

想查看原题可以点击题目链接。
简单地说，就是要求实现一个类，这个类能够返回数组中任意一个闭区间的数值和。

思路分享

这是前缀和的模板题，所谓前缀和的计算，正如其名，就是把数组从左往右一个个数值累加并记录。

https://leetcode.cn/problems/range-sum-query-immutable/solutions/2693498/qian-zhui-he-ji-qi-kuo-zhan-fu-ti-dan-py-vaar/
实现方式很简单，但是有一点需要特别注意，就是留出第一位的 0.如果采用第一位就放第一位的数值，那么就需要特别处理闭区间左部为 0 的情况，但是如果第一位置零，第二位放第一个数值，第三位放前两个数值，这样子下去，取区间和就只要调整一下下标加一即可。

代码解答（强烈建议自行解答后再看）

参考题解

class NumArray:

    def __init__(self, nums: List[int]):
        s = [0] * (len(nums)+1)
        for i,x in enumerate(nums):
            s[i+1] = s[i] + x
        self.s = s


    def sumRange(self, left: int, right: int) -> int:
        return self.s[right+1]-self.s[left]


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

文章作者: 陆爻齐-LuYaoQi

文章链接: http://hslix.github.io/posts/42905a7b.html

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 LuYaoQi's Blogs！

Algorithm 前缀和

相关推荐

【Leetcode Daily】1534统计好三元组

题目浅析想查看原题可以点击题目链接。简单地说，就是给一个数组，要求统计其中所有满足要求三元组的数量。该要求是，两两之差，满足题目的三个数字。思路分享首先就是暴力解法，O(n^3)，不过陆爻齐在普通的暴力上做了一点点剪枝，但终究还是暴力。想要比较好的完成本题，就需要学习前缀和，总体的思路是固定三元组中的两个，通过要求来求得剩下一个值的范围，将该范围在前缀和中搜寻，符合则找到合适的三元组。 https://leetcode.cn/problems/count-good-triplets/?envType=daily-question&envId=2025-04-14 代码解答（强烈建议自行解答后再看）陆爻齐小改良的暴力解法 12345678910111213141516171819class Solution {public: int countGoodTriplets(vector<int>& arr, int a, int b, int c) { int size =...

【Leetcode Daily】2389和有限的最长子序列

题目浅析想查看原题可以点击题目链接。简单地说，就是求一个数组的每个值，与另一个数组子序列和的关系，在子序列和不超过这个值的前提下，求最长子序列的长度。思路分享前缀和+二分 https://leetcode.cn/problems/longest-subsequence-with-limited-sum/solutions/1781111/fei-bao-li-zuo-fa-qian-zhui-he-er-fen-by-ny4m/ 为了使得子序列长度越长，要尽可能选取数值较小的元素。所以先排序，然后用前缀和得到各个子序列的和。具体实现中，前缀和用 numeric 库的 partial_sum 实现，而二分就直接用 ranges 库的 upper_bound 函数，之所以不用 lower_bound 是因为本题要求“不超过”，而非小于。当然，用加一值的lower_cound也行。代码解答（强烈建议自行解答后再看）参考题解 123456789101112class Solution {public: ...

【Leetcode Daily】3427变长子数组求和

题目浅析想查看原题可以点击题目链接。简单地说，就是给了一个整型数组，对其中的每一个元素，都要根据一个要求创建一个子数组，而题目要求则要返回这些所有子数组的数值和。思路分享前缀和的思路，可以参考【Leetcode Daily】303区域和检索-数组不可变由于题目子数组和求得的方式，可以通过前缀和方便完成，所以采用这种方法。重要的是，终于搞清楚了 Python 中 accumulate 函数到底是怎么形成的。对于 [1, 2, 3] 这样的列表，accumulate([1, 2, 3]) 会产生 [1, 3, 6]，也就是前缀和，但是通过增加参数 initial 的值可以改变初始前缀和值（该参数默认为 None），比如 accumulate([1, 2, 3], initial=0)，会在初始的地方增加一个 0，变成 [0, 1, 3, 6]；accumulate([1, 2, 3], initial=1)，就是 [1, 2, 4, 7]。代码解答（强烈建议自行解答后再看）参考题解 123456789class...

【Leetcode Daily】2559统计范围内的元音字符串数

题目浅析想查看原题可以点击题目链接。简单地说，就是给一个字符串和一个二维整数数组，二维数组内每个元素有两个数值，代表一个区间，要求返回每个区间内开头和结尾都是元音字母的数量。思路分享基本前缀和的思路，可以参考【Leetcode Daily】303区域和检索-数组不可变除了题目，几乎与昨日的题目一模一样（【Leetcode Daily】3427变长子数组求和），故不做赘述。只补充一点感受，还真是有点不习惯这个 accumulate 函数，还是得慢慢适应这种有各种方便函数调用的 Python ~（蛇堕*n） https://leetcode.cn/problems/count-vowel-strings-in-ranges/solutions/2093978/suan-fa-xiao-ke-tang-qian-zhui-he-by-end-n0mx/ 代码解答（强烈建议自行解答后再看）参考题解 123456789101112131415161718class Solution: def vowelStrings(self, words:...

【Leetcode Daily】1052爱生气的书店老板

题目浅析想查看原题可以点击题目链接。简单地说，就是给两个整型数组，以及一个整数 minutes，按某个要求（具体看原题，难以简化），求一个数组在另一个数组和 minutes 约束下的求的最大值。思路分享陆爻齐的思路是计算窗口内（也就是冷静的分钟）不满意生气离开的最大值，加上不生气的心情值，再减去所有生气离开的数值得出答案，但由于思想复杂了点，所以略微修改模板结构，也就是下面陆爻齐的答案。参照灵茶山艾府，其实只要区分开两部分相加即可，然后直接参照模板。这两部分，一个是不生气的值，一个是生气下的值，取生气下最大值即可。这样就不用像上面一样多一次运算。 https://leetcode.cn/problems/grumpy-bookstore-owner/solutions/2751888/ding-chang-hua-dong-chuang-kou-fu-ti-dan-rch7/ 代码解答（强烈建议自行解答后再看）陆爻齐的解法 12345678910111213141516171819202122232425class Solution...

【Leetcode Daily】1297子串的最大出现次数

题目浅析想查看原题可以点击题目链接。简单地说，就是给一个字符串，求满足要求的子串中，出现最多的次数。该要求为 1. 内部的字母数量小于 maxLetters；2. 整个字符串的长度在 minSize 和 maxSize 之间（闭区间）。思路分享该题的难度在于干扰项 maxSize，由于求子串尽可能多的出现，所以该子串的长度必然越小越好，就是 minSize。就是定长滑动窗口(【Leetcode Daily】1456定长子串中元音的最大数目)，有了个字母数量不大于 maxLetters 的限制，再用哈希统计满足要求字符串出现的次数即可。代码解答（强烈建议自行解答后再看）陆爻齐的解法 1234567891011121314151617181920212223242526272829class Solution {public: int maxFreq(string s, int maxLetters, int minSize, int maxSize) { vector<int>...

数据加载中