2022/05/17 Tue 12:24    2022/11/16 Wed 23:28

前缀和：

参考链接：https://zhuanlan.zhihu.com/p/260739067
https://mp.weixin.qq.com/s/48t0y13XB7URrkSR5A20Iw
这里我在写的时候还是需要注意关于原数组于前缀和数组的关系，自己也是做了一部分题目出来的，也不是完全什么都不懂的人，前缀和正好是原数组多一个。

  1. presum[i]就是num[0:i]的和（这里这里因为是python的语言，所以是不包含nums[i]的值，就是nums[i]前面的元素之和
  2. 下标索引为i~j之间的区间和=presum[j+1]-presumi
    用在求子数组和子串的问题上，求数列的和就是前n项和，技巧并不难，可以很好的处理数组区间的问题。

    通过前缀和数组保存前n位的和，可以轻松的得到每个区间的和（index从0开始），有点类似于字符串匹配算法BM KMP中的next数组和suffix数组的作用

相关练习题：

  1. leetcode 724. 寻找数组的中心索引
  2. leetcode 523 连续的子数组和
  3. leetcoad 560 和为K的子数组
  4. leetcoad974-和可被K整除的子数组；

leetcode 724. 寻找数组的中心索引

# 自己做的时候的思路如下，相对比较笨，先构建出前缀和数组，然后根据题目的意思找出相应的等量关系
# 这样做太浪费空间了，如果数值更大的话，会超出内存限制
class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        n=len(nums)
        presum=[0]
        sum=0
        # 创建出前缀和数组
        for i in range(n):
            sum+=nums[i]
            presum.append(sum)
        print(presum)
        # 对前缀和数组进行遍历
        # 如果发现抛开第一个数的所有和为0
        if presum[n]-nums[0]==0:
            return 0
        for i in range(1,n+1):
            # 如果发现相邻两个前缀和等于最后一个前缀和
            if presum[i-1]+presum[i]==presum[n]:
                return i-1
        return -1

对该方法进行改进，可以优化很多空间，不需要每次计算左半部分和右半部分的和，可以根据上一次计算的做左半部分和右半部分的和，以及新增或删除元素来获得当前左半部分和右半部分的和。合理的利用了数组的切分

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        # 第一个值
        a=sum(nums[:0])
        # 对切开第一个数之后的数组求和
        b=sum(nums[1:])
        for i in range(0,len(nums)-1):
            # 如果发现a==b，直接返回对应的i
            if a==b:
                return i
            # 继续向右移动，求左右两部分
            # 这里很容易忽略，a需要将nums[i]加入，b需要将nums[i+1]剔除
            a+=nums[i]
            b-=nums[i+1]
        # 当遍历到最后一个元素，即循环结束
        if a==b:
            return len(nums)-1
        else:
            return -1

leetcode 523 连续的子数组和


理清题目的要求：

  1. 子数组的大小至少为2
  2. 子数组元素总和为k的倍数，如果存在返回true，如果不存在就返回false
    首先想到的就是用暴力解法，发现果然是超时的，只能通过一部分的案例
class Solution: 
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        # 做题步骤
        # 1. 首先定义一个子数组
        # 2 .判断子数组的和是否等于k的整数倍
        # 3. 如果不是，就不停的添加新的元素重新计算
        n= len(nums)
        # 外层固定数组的长度，内存表示子数组第一个下标
        # 外层循环是子数组的长度,最短有两个，最长有n个
        for i in range(2,n+1):
            # 内层循环时子数组的第一个值的下标,下标的范围从0~n-i-1
            for j in range(n-i+1):
                a=sum(nums[j:j+i])
                # 如果a除以k的余数为0
                if a%k==0:
                    return True
        # 如果循环结束周仍然没有返回（没有找到和为k的倍数的）
        if n==2 and sum(nums)%k==0:
            return True
        else:
            return False

现在要对代码进行相应的优化，用到前缀和和哈希表的知识
看到几项的和为条件的判断，考虑前缀和，同时引入同余定理（当两个数除以每个数的余数相等，两者相减之后肯定可以被该数整除，这里其实可以简单的知道一些证明的过程），采用前缀和方式进行判断，后面的数字总和必然包含它之前的内容，维护一个hash表，记录{余数：下标}，存在前n个数字恰好被k整除的情况，预制一个字典{0：-1}来规避这样的问题

在利用的时候，没有把列表全部更新一遍，只要更新列表每个字段为前缀和内容再二次判断（自己理解：如果全部循环必然会很费时间，更新presum遍历一遍，用的时候可能还要再遍历一遍），所以在需要多次循环列表的时候，我们只需要维护一个初始值为0的数字，每次加等就可以

# 写出符合自己的方法
from typing import List
class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        # 创建字典
        hashmap=dict()
        # 添加一个初始值,添加初始值的原因保证和数组的索引同步（这里的构造方法和560题的思考方式是一致的，注意运用的情况）
        hashmap[0]=-1
        # 一边构造前缀和一边用哈希表进行查找
        presum=0
        for index,num in enumerate(nums):
            presum+=num
            # 取前缀和
            # 整除k的余数
            rem=presum%k
            # 如果发现该余数不在哈希表中,就将余数与当前的索引作为键和值加入hashmap中
            if rem not in hashmap:
                hashmap[rem]=index
            # 如果发现余数已经在哈希表中,这个时候就要看此时的索引与之前的索引的差值有没有大于等于2
            else:
                # 用get()函数获取之前的索引
                i = hashmap.get(rem)
                #print(i)
                # 比较现在的索引与原索引的差值
                if index -i >=2:
                    return True
        return False

# 主函数
if __name__=='__main__':
    nums=[1,2,3]
    res=Solution().checkSubarraySum(nums,6)
    print(res)

leetcoad 560 和为K的子数组

参考链接：https://leetcode-cn.com/problems/subarray-sum-equals-k/solution/python3-by-wu-qiong-sheng-gao-de-qia-non-w6jw/
以下的解法都是在实操的层面不断的进行相应的优化的，其实也是十分的灵活的，所以自己要不断的敲才能认真的掌握。在平时的练习的时候确实是值得反复的思考，让自己的思维活跃起来，真正的把前缀和运用好。
储备知识：怎么求一个数组的连续子数组（只是为了理解题意，也是为后面的代码做出一定的参考）

nums=[1,2,3]
n=len(nums)
subnums=[]
for i in range(n):
    for j in range(i,n):
        subnums.append(nums[i:j+1])
print(subnums)
#输出结果
[[1], [1, 2], [1, 2, 3], [2], [2, 3], [3]]

暴力的解法，是有一些案例通不过的，并且是超时的（自己想的写法）

# 90个案例通过61个
class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        count=0
        # 外层循环表示数组的长度
        for i in range(1,n+1):
            # 内层循环，记录子数组第一个下标的变化范围
            for j in range(0,n-i+1):
                # 统计子数组的和
                if sum(nums[j:j+i])==k:
                    count+=1
        return count

仍然是暴力解法（可能也是最直接的理解层面上的东西）
时间复杂度O(n^3):两层循环还有一层求和的过程

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        count=0
        for i in range(n):
            for j in range(i,n):
                # 充分利用了nums切片的性质
                if sum(nums[i:j+1])==k:
                    count +=1
        return count

在上面的基础上继续进行优化：将时间复杂度优化为O(n^2)
这里优化的点在于：在求nums[i:j+1]的下一次nums[i:j+1+1]的时候，不需要哉从i开始算了，直接哉上一次的结果上+nums[j+1],但是记住内层循环结束的时候需要将sum置0（如果不置0，会一直累加，这样并不是区间的和）
双循环，仍然是超出时间限制,90个案例通过72个

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        count=0
        sum=0
        for i in range(n):
            for j in range(i,n):
                sum+=nums[j]
                if sum==k:
                    count+=1
            sum=0
        return count

要计算i和j之间的和：nums[i]+nums[i+1]+⋯+nums[j]
可以看作是nums[0]+nums[1]+⋯+nums[i]+nums[i+1]+⋯+nums[j] 减去 nums[0]+nums[1]+⋯+nums[i−1]
也即：preSum[j]−preSum[i−1]
操作如下：先遍历一次数组，求出前缀和数组，用这个数组代替最开始的暴力解法的sum函数

from typing import List
class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        n=len(nums)
        subnums=[0]

        # 求前缀和数组的过程
        temp=0
        for i in range(n):
            temp+=nums[i]
            subnums.append(temp)
        # print(subnums)
        # 求和为k的连续子数组出现的次数
        count=0
        # 这里要注意相应的下标,subnums的长度为n+1,下标从1开始
        for i in range(1,n+1):
            for j in range(i,n+1):
                if subnums[j]-subnums[i-1]==k:
                    count+=1
        return count

# 主函数
if __name__=='__main__':
    nums=[1,1,1]
    res=Solution().subarraySum(nums,2)
    print(res)

再进一步优化，边计算前缀和边统计这个过程，只关心次数，不关心具体的解，用哈希表加速运算，由于保存了之前相同前缀和的数目，计算区间总数的时候不是一个个加的，时间复杂度减低到O(N)
优化的过程也要采用前缀和+hashmap的思路，有点两数之和的味道，将所有的前缀和和该前缀出现的次数存放到字典中，用下面的这张图来进行辅助理解(这种思路也就是在做题的时候才会认认真真的想的到的方式，也是一种很巧妙的方式，主要在于理解哈希表的存放数据)

计算到i位置的前缀和（包含i）-目标k在字典中出现的次数，假设出现过m次，代表第i位以前（不含i）有m个连续子数组的和为presum-k。每一个都可以和presum组成为presum-(presum-k)=k
备注：自己实操的时候才发现有几个大坑，自己可能平时都没有怎么注意到这个问题，对if else语句的理解并不是特别的到位，特别是一些关键的位置，这里贴两份代码，其中一份是错的（用图片的形式），另一份是正确的。这种错误错误坚决不能够再犯了。

# 正确的代码
from typing import List
class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        # 采用前缀和+哈希表
        count=0
        # 创建字典，字典存储的是前缀和以及前缀和出现的次数，并将0：1加入字典中
        # 加入的原因：在开始的时候，和为0的情况发生了一次（这是比较容易忽略的地方）
        hashmap={0:1}
        # 统计前缀和
        presum=0
        # 对nums进行遍历，并统计相应的前缀和
        for i in range(len(nums)):
            presum+=nums[i]
            # 查看presum-k是否在hashmap中存在，如果存在的话，那么presum-k出现的次数就是连续子数组为k出现的次数
            if presum-k in hashmap:
                count+=hashmap[presum-k]
            hashmap[presum]=hashmap.get(presum,0)+1
        return count

if __name__=='__main__':
    nums=[1,2,3]
    res=Solution().subarraySum(nums,3)
    print(res)

leetcoad974-和可被K整除的子数组

还是一样，先是常规思路

class Solution:
    def subarraysDivByK(self, nums: List[int], k: int) -> int:
        n=len(nums)
        count=0
        sum=0
        for i in range(n):
            for j in range(i,n):
                sum+=nums[j]
                if sum%k==0:
                    count+=1
            sum=0
        return count

先将前缀和处理，然后计算子数组和能够被k整除的情况

class Solution:
    def subarraysDivByK(self, nums: List[int], k: int) -> int:
        n = len(nums)
        count=0
        presum=[0]
        temp=0
        for i in range(n):
            temp+=nums[i]
            presum.append(temp)
        
        # 在前缀和数组中找子数组的和可以被k整除的情况，在区间[i:j+1]的范围内presum[j]-presum[i]
        # 外层循环是前缀和数组的下标，从下标0开始,总共有n+1个数，n个下标
        for i in range(n+1):
            # 内层循环时，下标从i+1
            for j in range(i+1,n+1):
                # 计算子数组的和是否可以被k整除
                if (presum[j]-presum[i])%k==0:
                    count+=1
                    # 这里多加了一行满足条件的子数组的打印，可以更好的理解这里的过程
                    print(nums[i:j+1])
        return count

if __name__=='__main__':
    nums=[4,5,0,-2,-3,1]
    res=Solution().subarraysDivByK(nums,5)
    print(res)

# 针对分步的输出结果
[4, 5, 0, -2, -3, 1]
[5, 0]
[5, 0, -2]
[5, 0, -2, -3, 1]
[0, -2]
[0, -2, -3, 1]
[-2, -3, 1]

采用前缀和+哈希表的方式
这里贴一张自己的理解过程，终于在理解的基础上通过了这道题，并且可以说对哈希表有了一个比较深的认识

class Solution:
    def subarraysDivByK(self, nums: List[int], k: int) -> int:
        # 采用前缀和+哈希表的知识
        # 构建一个哈希表，并传入0：1
        # 其中哈希表中存入的是余数：余数出现的次数
        hashmap={0:1}
        # 统计能够被k整除的数目
        count=0
        # 统计前缀和
        presum=0
        # 开始进行遍历并统计，采用边遍历，边哈希查找的方式
        for num in nums:
            # 更新前缀和
            presum+=num
            # 取前缀和与k除的余数
            rem=presum%k
            # 采用同余定理，并用哈希表进行查找
            if rem in hashmap:
                count+=hashmap[rem]
            hashmap[rem]=hashmap.get(rem,0)+1
        return count
ToTOP
2018 bear