本文基于各個大佬的文章
上點關注下點贊，明天一定更燦爛！
前言
????????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。
總結
? ? ? ? 只會打暴力，基礎一團糟，明天再學吧老鐵，別真學會了。
)！)
