竞价恶意点击器,phpcms网站seo怎么做,优秀设计师个人网站,太原谁想做网站【LetMeFly】303.区域和检索 - 数组不可变#xff1a;前缀和#xff08;两行描述核心思路版本#xff09;
力扣题目链接#xff1a;https://leetcode.cn/problems/range-sum-query-immutable/
给定一个整数数组 nums#xff0c;处理以下类型的多个查询:
计算索引 left…【LetMeFly】303.区域和检索 - 数组不可变前缀和两行描述核心思路版本
力扣题目链接https://leetcode.cn/problems/range-sum-query-immutable/
给定一个整数数组 nums处理以下类型的多个查询:
计算索引 left 和 right 包含 left 和 right之间的 nums 元素的 和 其中 left right
实现 NumArray 类
NumArray(int[] nums) 使用数组 nums 初始化对象int sumRange(int i, int j) 返回数组 nums 中索引 left 和 right 之间的元素的 总和 包含 left 和 right 两点也就是 nums[left] nums[left 1] ... nums[right] ) 示例 1
输入
[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))提示
1 nums.length 104-105 nums[i] 1050 i j nums.length最多调用 104 次 sumRange 方法
方法一前缀和
这道题唯一需要掌握的思路是使用一个 p r e f i x prefix prefix数组预处理使 p r e f i x [ i ] ∑ 0 i − 1 n u m s [ i ] prefix[i]\sum_0^{i-1} nums[i] prefix[i]∑0i−1nums[i]。
这样 ∑ l e f t r i g h t \sum_{left}^{right} ∑leftright就等于 p r e f i x [ r i g h t 1 ] − p r e f i x [ l e f t ] prefix[right1]-prefix[left] prefix[right1]−prefix[left]了。
时间复杂度初始化 O ( l e n ( n u m s ) ) O(len(nums)) O(len(nums))查询 O ( 1 ) O(1) O(1)每次空间复杂度 O ( l e n ( n u m ) ) O(len(num)) O(len(num))因为标题说“数组不可变”否则直接修改原数组能把空间复杂度将为 O ( 1 ) O(1) O(1)
AC代码
C
class NumArray {
private:vectorint prefix;
public:NumArray(vectorint nums) {prefix.resize(nums.size() 1);for (int i 0; i nums.size(); i) {prefix[i 1] prefix[i] nums[i];}}int sumRange(int left, int right) {return prefix[right 1] - prefix[left];}
};Python
# from typing import Listclass NumArray:def __init__(self, nums: List[int]):self.prefix [0] * (len(nums) 1)for i in range(len(nums)):self.prefix[i 1] self.prefix[i] nums[i]def sumRange(self, left: int, right: int) - int:return self.prefix[right 1] - self.prefix[left]同步发文于CSDN和我的个人博客原创不易转载经作者同意后请附上原文链接哦~ Tisfyhttps://letmefly.blog.csdn.net/article/details/136801479
