Closed labuladong closed 1 year ago
Q303. Range Sum Query - Immutable https://leetcode.com/problems/range-sum-query-immutable/discuss/3854818/Java-prefix-solution
Q304. Range Sum Query 2D - Immutable https://leetcode.com/problems/range-sum-query-2d-immutable/discuss/3854827/Java-prefix-solution
[304. Range Sum Query 2D - Immutable] https://leetcode.com/problems/range-sum-query-2d-immutable/solutions/3855792/prefix-sum/
https://leetcode.cn/problems/range-sum-query-immutable/solution/qu-yu-he-jian-suo-yi-wei-shu-zu-by-6ifte-djsf/ https://leetcode.cn/problems/range-sum-query-2d-immutable/solution/er-wei-qu-yu-jian-suo-by-6ifted-vvrightj-n6cc/ https://leetcode.cn/problems/subarray-sum-equals-k/solution/he-wei-kde-zi-shu-zu-by-6ifted-vvrightj2-f1b6/
https://leetcode.cn/problems/range-sum-query-immutable/solutions/2371679/qian-zhui-he-zhu-yi-java-yu-yan-ru-he-di-29lh/ 前缀和。注意 Java 语言如何定义数组,如何给数组赋值,构造方法没有返回值等。
class NumArray {
// 初始化前缀和数组,注意初始化数组的写法
private int[] preSum;
public NumArray(int[] nums) {
// 赋值的时候不用写 int[]
preSum = new int[nums.length + 1];
// 根据 nums 构造前缀和数组 preSum
for (int i = 1; i < preSum.length; i++) {
preSum[i] = preSum[i - 1] + nums[i - 1];
}
// 构造方法没有返回值
}
public int sumRange(int left, int right) {
return preSum[right + 1] - preSum[left];
}
}
/**
* Your NumArray object will be instantiated and called as such:
* NumArray obj = new NumArray(nums);
* int param_1 = obj.sumRange(left,right);
*/
详细理解下标index的问题,很容易写错 1.构造presum数据 核心思想 原数组的 presum[i-1] 累加值 + nums[i-1] 原数组值 一起作为下一个前缀和 因为错位1,presum要比 nums长1位,留了一个0,所以index要i-1来进行 前一个的累加+原数组的 pre [2] = pre[1]+nums[1]
def __init__(self, nums: List[int]):
presum =[0]* len((nums)+1) # 构造为0数组
for i in range(1,len(presum)) # 错一位进行开始
presum[i] = presum[i-1]+ nums[i-1]
def sumRange(self, left: int, right: int) -> int:
return self.presum[right+1] - self.presum[left]
2.定范围查找 思维转化,将原数组nums left累加到right的加法问题转换为dual的相减问题, 例如 cumlative [3~7] = 3+4+5+6+7 Dual:从1+到7的presum[7+1] - presum[3] 注意这里我们因为做了偏移presum的第一个数字是0,index是0,所以是presum[8]才能是01234567
作者:RaydenX 链接:https://leetcode.cn/problems/range-sum-query-immutable/solutions/2372216/qian-zhui-he-lei-ji-lei-ji-chai-de-si-we-93pu/
本期打卡已结算完成。报名最新一期的打卡活动 点这里