7 Subarrays (prefix sum)
这类题用到prefix sum。感觉sliding window求size，subarrays求sum/具体下标。
prefix的array/matrix留空前面一个格子/一行一列来算比较方便，用的时候把j +1减去 i 就好了。
6年后发现，还有一类是用hashmap来算prefix/suffix的
基础题：
303 Range Sum Query - immutable -- prefixSum
304 Range Sum Query 2D - immutable -- prefix Sum
L558 Sliding Window Matrix Maximum
1310 XOR Queries of a Subarray -- 套着xor皮的prefix sum
Max/Min :
L41 Maximum Subarray(53) -- L402求下标
L45 Maximum Subarray Difference
L620 Maximum Subarray IV
L621 Maximum Subarray V
L617 Maximum Average Subarray (2分，留意2分讲座笔记）
523 Continuous Subarray Sum -- 感觉有点2分的意味，有空看看
首尾链接：
L403 Continuous Subarray Sum II -- 有环
L402 Continuous Subarray Sum -- L41求max值，这里求具体下标。
DP：
L43 Maximum Subarray III (DP -- 划分类)
L191 Maximum product Subarrays (DP) （152）
Stock 3（DP -- 划分类）
hash or 2分：-- 有点像在用hashmap做dp的感觉
L138 Subarray Sum -- hash
L405 Submatrix Sum --L138进化版
L404 Subarray Sum II -- 用2分优化
325 Maximum Size Subarray Sum Equals k -- 感觉又是一个L138的变种
523 Continuous Subarray Sum -- L138又变，这次来个mod
525 Contiguous Array -- 又一个L138
1477 Find Two Non-overlapping Sub-arrays Each With Target Sum
变体or相关：
other related：
713 Subarray Product Less Than K
724 Find Pivot Index -- 某次contest的题
308 Range Sum Query 2D - Mutable -- segment tree or BIT
307 Range Sum Query - Mutable -- segment tree or BIT
L643 Longest Absolute File Path (388) -- 实现上可以用prefix sum数组或者stack
Last updated