前缀和学习笔记

朴灿烈づ我的快乐病毒、 2024-03-31 13:51 70阅读 0赞

#### 首先了解下滑动窗口: ####

滑动窗口是解决求连续子数组的相关问题的经典解法.该问题的模板如下:

1.确定左右边界

2.查找滑动的条件和方式

3.按照题意套用模板

滑动窗口的局限性:

如果数组中出现负值元素,那么窗口的边界是应该左侧收缩还是右侧延展就出现了争议.

#### 前缀和思想: ####

当循环遍历到数组下标N的时候,我们可能用到前面的N-1项的计算结果,这种计算结果可能是加和的结果,也可能是累积等.此时应该考虑的是怎么样通过计算数组循环过程中的累计值来简化解题.

那么这个累计和的结果通过什么方式保存起来呢:

1.题目要求不允许使用额外空间: 直接原地修改数组

2.不限制空间复杂度,最好额外开辟空间计算,避免数据污染

3.计算时如果每次只需要获取前一次的累计结果,那么可以通过数组的方式来每次获取数组末尾的值

4.若果每次计算需要获取前几次或者更多的累计结果表示,推荐使用哈希表的方式,可以压缩时间复杂度

例题:

> 给定一个整数数组和一个整数 k ，请找到该数组中和为 k 的连续子数组的个数。
> 
> 提示:
> 
> 1 <= nums.length <= 2 \* 10 ^ 4  
> \-1000 <= nums\[i\] <= 1000  
> \-10 ^ 7 <= k <= 10 ^ 7  
> 示例  
> 示例 1 :  
> 输入:nums = \[1,1,1\], k = 2  
> 输出: 2  
> 解释: 此题 \[1,1\] 与 \[1,1\] 为两种不同的情况
> 
> 示例 2 :  
> 输入:nums = \[1,2,3\], k = 3  
> 输出: 2

https://leetcode-cn.com/problems/QTMn0o/solution/shua-chuan-jian-zhi-offer-day07-shu-zu-i-jdnu/

解析:如果没有负数的话,用滑动窗口的思想:

def subarraySum(self, nums: List[int], k: int) -> int:
        left = right = 0
        temp = res = 0
        while right < len(nums):
            temp += nums[right]
            while temp > k and left < right:
                temp -= nums[left]
                left += 1
            if temp == k:
                res += 1
                temp -= nums[left]
                left += 1
            right += 1
        return res

存在负数,用前缀和:

class Solution {
        public int subarraySum(int[] nums, int k) {
            int preSum = 0;
            int re = 0;
            HashMap<Integer ,Integer> map = new HashMap<Integer,Integer>();
            map.put(0,1);
            for(int i: nums){
                preSum += i;
                re += map.getOrDefault(-k + preSum,0);
                map.put(preSum,map.getOrDefault(preSum,0)+1);
            }
            return re;
        }
    }

具体思路如下：

1.初始化一个空的哈希表和pre\_sum=0的前缀和变量  
2.设置返回值ret = 0，用于记录满足题意的子数组数量  
3.循环数组的过程中，通过原地修改数组的方式，计算数组的累加和  
4.将当前累加和减去整数K的结果，在哈希表中查找是否存在  
5.如果存在该key值，证明以数组某一点为起点到当前位置满足题意，ret加等于将该key值对应的value  
6.判断当前的累加和是否在哈希表中，若存在value+1，若不存在value=1  
7.最终返回ret即可

但在这里要注意刚才说到的前缀和边界问题。 我们在计算这种场景时，需要考虑如果以数组nums\[0\]为开头的连续子数组就满足题意呢？ 此时候我们的哈希表还是空的，没办法计算前缀和！所以遇到这类题目，都需要在哈希表中默认插入一个\{0:1\}的键值对， 用于解决从数组开头的连续子数组满足题意的特殊场景。

对于第五条:

为什么map中的键对应的值是可以证明为从某一起点到当前位置的累加和是满足题意的 ?

在代码中我们不断的累加和,那么将这个累加和与k做差得到的数的意义为: 当前的累加和比k多了多少(这个值可能是负的),那么很自然的,我们在map中存的数据的key值的意义是存在这样的连续的数,使得其和为key,那么从可以对应位置的结束到当前的累加和的位置的总和值正好就是k

用公式推导就是 : 已知 cur(总的累加和) - k = 前面某一段的累加和(key)

那么 cur - key = k (移项)