LeetCode100-560和为K的子数组
本文基于各个大佬的文章
上点关注下点赞，明天一定更灿烂！
前言
Python基础好像会了又好像没会，所有我直接开始刷leetcode一边抄样例代码一边学习吧。本系列文章用来记录学习中的思考，写给自己看的，也欢迎大家在评论区指导~
您的每一条评论都会让我更有学习的动力。
一、分析题目
本题目分组是【子串】
子串（Substring） 是指字符串中连续的字符序列，由原字符串中任意位置开始、任意位置结束的连续字符组成。
示例：对于字符串 "abcde"
- 长度为 1 的子串："a", "b", "c", "d", "e"
- 长度为 2 的子串："ab", "bc", "cd", "de"
- 长度为 3 的子串："abc", "bcd", "cde"
- 以此类推，最长子串是原字符串本身
子串 vs 子序列
子串是连续的，子序列可以是非连续的但保持顺序。
| 特性 | 子串（Substring） | 子序列（Subsequence） |
|---|---|---|
| 连续性 | 必须连续 | 可以不连续 |
| 字符顺序 | 保持原顺序 | 保持原顺序 |
| 数量 | n (n+1)/2 个非空子串 | 2ⁿ-1 个非空子序列 |
| 示例（"abc"） | "a", "b", "c", "ab", "bc", "abc" | "a", "b", "c", "ab", "ac", "bc", "abc” |
本题的题目是子数组，那么他们两者的关系是什么呢
- 子串：用于字符串，由字符组成的连续序列
- 子数组：用于数组，由元素组成的连续序列
二、思路以及代码
思路：子数组是由元素组成的连续序列，可以借助滑动窗口，而且是长度可变的滑动窗口
class Solution:def subarraySum(self, nums: List[int], k: int) -> int:sum=0left=0count=0for right in range(len(nums)):sum+=nums[right]while sum>k and left<=right:sum-=nums[left]left+=1if sum==k:count+=1return count提交之后答案是错误的，我重新回去看了题目要求，要求数组的数字可能含有负数，所有我这个办法是不能这么写的。
看看其他办法。问了一下deep老师，老师说因为数组不是非负数，所有负数可能会导致窗口内数字和变大或者变小，移动策略无法处理。推荐的方法是使用前缀和+哈希表（字典）实现。
我们先来了解一下什么是前缀和吧。
前缀和的概念：前缀和是一种预处理技巧，用于快速计算数组中某段子数组的元素的总和。
定义：对于一个数组
nums，它的前缀和数组prefix_sums的定义如下：prefix_sums[i]=nums[0] + nums[1] + ... + nums[i]，i从0开始。nums = [1, 2, -1, 3, 4] prefix_sums = [1, 3, 2, 5, 9] # 计算方法： 1, 1+2, 1+2-1, 1+2-1+3, 1+2-1+3+4
对于这个题目，我们可以设置一个哈希表，哈希表的key是前缀和，value是这个前缀和出现的次数。也是就我们想要求得前缀和为k，然后value是k出现的次数，也就是我们最后求的子串组数。
from typing import Listdef subarraySum(nums: List[int], k: int) -> int:count = 0prefix_sum = 0prefix_sums = {0: 1} # 初始化，前缀和为0时出现一次（代表空子数组的和为0）for num in nums:prefix_sum += num # 计算当前的前缀和# 查看是否存在前缀和为 current_sum - kif (prefix_sum - k) in prefix_sums: # 这个时候，如果存在，说明从之前的某个位置到当前位置的和正好是kcount += prefix_sums[prefix_sum - k] # 出现多少次，就加上多少，比如prefix_sums[prefix_sum - k] = 3,说明之前有3个满足条件的前缀和，所以count要增加3# 更新字典中的前缀和出现次数prefix_sums[prefix_sum] = prefix_sums.get(prefix_sum, 0) + 1 # 更新哈希表，当前的前缀和出现了多少次return count
成功通过
三、本题收获
prefix_sums[prefix_sum] = prefix_sums.get(prefix_sum, 0) + 1prefix_sums 字典中获取键 prefix_sum 对应的值。
如果 prefix_sum 作为键存在于字典中，则 get() 方法返回该键对应的值（也就是该前缀和出现的次数）。
如果 prefix_sum 作为键不存在于字典中，则 get() 方法返回第二个参数的值作为默认值，这里是 0。
总结
只会打暴力，基础一团糟，明天再学吧老铁，别真学会了。