• 子數(shù)組的定義是原來的數(shù)組當(dāng)中連續(xù)的非空的序列，而我們的背包問題的選與不選的情況，對應(yīng)的是這個(gè)非連續(xù)的情況,那么這種情況就要注意
• 當(dāng)然啦，對于線性的時(shí)間內(nèi)解決的問題我們可能會想到使用滑動(dòng)窗口進(jìn)行處理的問題，但是應(yīng)該要注意 滑動(dòng)窗口只適合用于單調(diào)的情況，也就是說nums數(shù)組是全部為非負(fù)數(shù)或者非正數(shù)的情況
  • 我們所使用能夠使用滑動(dòng)窗口求解這個(gè)子數(shù)組的和為k的情況，基于的理念就是，控制滑動(dòng)窗口的l和r，當(dāng)<k的時(shí)候，窗口向右邊擴(kuò)大，>k的情況，就窗口左邊縮小，這個(gè)理論必須是基于單調(diào)的，也就是窗口越大，這個(gè)窗口的和值就越大
• 對于前綴和來說，適用的場景就沒有那么多的限制，任意的子數(shù)組之和都可以轉(zhuǎn)化為前綴和的差

前綴和與查分的補(bǔ)充

• 這個(gè)前綴和與哈希表的組合，有求解方案數(shù)(和為k值的方案數(shù))，那么記錄的是每種和值所出現(xiàn)的次數(shù)，對于長度問題來說，就是統(tǒng)計(jì)每種和值所出現(xiàn)的最小的下標(biāo)

使用前綴和+哈希表

560.和為K的子數(shù)組

560.和為K的子數(shù)組

思路分析

• 首先求解的是連續(xù)的情況，所以考慮使用滑動(dòng)窗口以及這個(gè)前綴和，但是由于存在正數(shù)和負(fù)數(shù)同時(shí)存在，所以就只能使用這個(gè)前綴和+哈希表

from collections import defaultdict
class Solution:def subarraySum(self, nums: List[int], k: int) -> int:# 不單調(diào)，不能使用這個(gè)滑動(dòng)窗口# 使用前綴和，但是為了不用兩層循環(huán)進(jìn)行遍歷，所以我們得使用一個(gè)哈希表進(jìn)行處理n = len(nums)store = defaultdict(int)pre = [0]*(n+1)for i in range(n):pre[i+1] = pre[i] + nums[i]# pre[i] - pre[j] = k ,那么只需在哈希表中查詢這個(gè)pre[i] - k 的個(gè)數(shù)即可ans = 0# 注意這個(gè) 0:1也要加進(jìn)去for i in range(n+1):ans += store[pre[i] - k]store[pre[i]] += 1return ans

525.連續(xù)數(shù)組

525.連續(xù)數(shù)組

• 參照和為k的子數(shù)組的思路，但是你會發(fā)現(xiàn)一個(gè)問題，這個(gè)0,1的統(tǒng)計(jì)時(shí)分難統(tǒng)計(jì)，難道要直接分別統(tǒng)計(jì)0和1各自的數(shù)量嗎？
• 當(dāng)然不是，所以得進(jìn)行巧妙的轉(zhuǎn)換：把這個(gè)0替換成-1,然后我們只需統(tǒng)計(jì)這個(gè) 和為0最長子數(shù)組即可，在使用哈希表的時(shí)候，我們不是記錄這個(gè)某個(gè)和值的出現(xiàn)的次數(shù)，而是改為記錄該和值出現(xiàn)的最小的下標(biāo)

class Solution:def findMaxLength(self, nums: List[int]) -> int:n = len(nums)newnum = [0]*n # 進(jìn)行轉(zhuǎn)化for i in range(n):if nums[i] == 0:newnum[i] = -1else:newnum[i] = 1# 求解前綴和pre = [0]*(n+1)for i in range(n):pre[i+1] = pre[i] + newnum[i]store = {}ans = 0for i in range(n+1):# 判斷該鍵是否出現(xiàn)過if pre[i] in store.keys():ans = max(ans,i - store[pre[i]])else:store[pre[i]] = ireturn ans

2588.統(tǒng)計(jì)美麗子數(shù)組數(shù)目

2588.統(tǒng)計(jì)美麗子數(shù)組數(shù)目

• 子數(shù)組是全部為0，也就是和值為0，那么對于減去的每一位來說，其實(shí)就是要求對應(yīng)位數(shù)上的1是偶數(shù)個(gè)數(shù)的，對于判斷是否是偶數(shù)個(gè)1，那么我們直接考慮使用這個(gè) 異或進(jìn)行操作，也就是 異或值為0的子數(shù)組的個(gè)數(shù)情況

from collections import defaultdict
class Solution:def beautifulSubarrays(self, nums: List[int]) -> int:# 求解方案數(shù)n = len(nums)# 異或前綴pre = [0]*(n+1)for i in range(n):pre[i+1] = pre[i]^nums[i]store = defaultdict(int)# 遍歷ans = 0for i in range(n+1):ans += store[pre[i]]store[pre[i]] += 1return ans