7 Subarrays (prefix sum)
Last updated
Was this helpful?
Last updated
Was this helpful?
这类题用到prefix sum。感觉sliding window求size，subarrays求sum/具体下标。
prefix的array/matrix留空前面一个格子/一行一列来算比较方便，用的时候把j +1减去 i 就好了。
6年后发现，还有一类是用hashmap来算prefix/suffix的
基础题：
-- prefixSum
-- prefix Sum
-- 套着xor皮的prefix sum
Max/Min :
(53) -- L402求下标
L620 Maximum Subarray IV
L621 Maximum Subarray V
L617 Maximum Average Subarray (2分，留意2分讲座笔记）
523 Continuous Subarray Sum -- 感觉有点2分的意味，有空看看
首尾链接：
DP：
hash or 2分：-- 有点像在用hashmap做dp的感觉
变体or相关：
other related：
都有点prefix Sum
-- 有环
-- L41求max值，这里求具体下标。
(DP -- 划分类)
(DP) （152）
（DP -- 划分类）
-- hash
--L138进化版
-- 用2分优化
-- 感觉又是一个L138的变种
-- L138又变，这次来个mod
-- 又一个L138
-- 某次contest的题
-- segment tree or BIT
-- segment tree or BIT
-- 实现上可以用prefix sum数组或者stack