數(shù)組元素和與數(shù)字和的絕對差

【遍歷】遍歷的時候算元素和及數(shù)位和。小優(yōu)化：不用abs，元素和必然大于數(shù)位和的和。

子矩陣元素加 1

【二維差分】模板題。二維前綴和：preSum[i] [j] = preSum[i-1] [j] + preSum[i] [j-1] - preSum[i-1] [j-1] + matrix[i] [j]。一維差分： arr 的區(qū)間 [l, r] 加一個值 v 等價于將差分?jǐn)?shù)組中的 diff[l] + v，再將 diff[r + 1] - v。差分?jǐn)?shù)組的前綴和相當(dāng)于原數(shù)組。二維差分：以(x1, y1)為左上角，(x2, y2)為右下角的子矩陣中的所有元素加上v： S[x1, y1] += v, S[x2 + 1, y1] -= v, S[x1, y2 + 1] -= v, S[x2 + 1, y2 + 1] += v

統(tǒng)計好子數(shù)組的數(shù)目

【雙指針】用一個哈希表統(tǒng)計滑動窗口內(nèi)每個元素出現(xiàn)次數(shù)cnt = Counter()。枚舉右端點(diǎn)nums[right]，窗口內(nèi)每囊括一個nums[right]，對數(shù)增加cnt[right]對。如果left右移一步，那么使得對數(shù)減少cnt[nums[left] - 1對，如果目前的對數(shù)pairs - (cnt[nums[left] - 1)仍然≥k，那么可以放心減掉左端點(diǎn)。左端點(diǎn)自身和其左邊都可以作為好子數(shù)組的左端點(diǎn)，所以每遍歷到一個nums[right]，ans += left + 1。

最大價值和與最小價值和的差值

【樹上DP】最小的一條路徑就一個節(jié)點(diǎn)，開銷等于一條路徑減一個節(jié)點(diǎn)。路徑越大越好，路徑兩端必然是度數(shù)為1的點(diǎn)，類似樹的直徑。