[[382488]]

什么是前綴和?

前綴和是一種重要的預(yù)處理，能大大降低查詢的時(shí)間復(fù)雜度。我們可以簡(jiǎn)單理解為“數(shù)列的前 n 項(xiàng)的和”。這個(gè)概念其實(shí)很容易理解，即一個(gè)數(shù)組中，第 n 位存儲(chǔ)的是數(shù)組前 n 個(gè)數(shù)字的和。

通過(guò)一個(gè)例子來(lái)進(jìn)行說(shuō)明會(huì)更清晰。題目描述：有一個(gè)長(zhǎng)度為 N 的整數(shù)數(shù)組 A，要求返回一個(gè)新的數(shù)組 B，其中 B 的第 i 個(gè)數(shù) B[i]是「原數(shù)組 A 前 i 項(xiàng)和」。

這道題實(shí)際就是讓你求數(shù)組 A 的前綴和。對(duì) [1,2,3,4,5,6] 來(lái)說(shuō)，其前綴和可以是 pre=[1,3,6,10,15,21]。我們可以使用公式 pre[??]=pre[???1]+nums[??]得到每一位前綴和的值，從而通過(guò)前綴和進(jìn)行相應(yīng)的計(jì)算和解題。其實(shí)前綴和的概念很簡(jiǎn)單，但困難的是如何在題目中使用前綴和以及如何使用前綴和的關(guān)系來(lái)進(jìn)行解題。實(shí)際的題目更多不是直接讓你求前綴和，而是你需要自己「使用前綴和來(lái)優(yōu)化算法的某一個(gè)性能瓶頸」。

而如果數(shù)組是正數(shù)的話，前綴和數(shù)組會(huì)是一個(gè)單調(diào)不遞減序列，因此前綴和 + 二分也會(huì)是一個(gè)考點(diǎn)，不過(guò)這種題目難度一般是力扣的困難難度。關(guān)于這個(gè)知識(shí)點(diǎn)，我會(huì)在之后的「二分專題」方做更多介紹。

簡(jiǎn)單的二維前綴和

上面提到的例子是一維數(shù)組的前綴和，簡(jiǎn)稱一維前綴和。那么二維前綴和實(shí)際上就是二維數(shù)組上的前綴和了。一維數(shù)組的前綴和也是一個(gè)一維數(shù)組，同樣地，二維數(shù)組的前綴和也是一個(gè)二維的數(shù)組。

比如對(duì)于如下的一個(gè)二維矩陣：

1 2 3 4 
5 6 7 8 

定義二維前綴和矩陣 ，。經(jīng)過(guò)這樣的處理，上面矩陣的二維前綴和就變成了：

1  3  6 10 
6 14 24 36 

那么如何用「代碼」計(jì)算二維數(shù)組的前綴和呢?簡(jiǎn)單的二維前綴和的求解方法是基于「容斥原理」的。

比如我們想求如圖中灰色部分的和。

一種方式就是用下圖中兩個(gè)綠色部分的矩陣加起來(lái)(之所以用綠色部分相加是因?yàn)檫@兩部分已經(jīng)通過(guò)上面預(yù)處理計(jì)算好了，可以在 的時(shí)間得到)，這樣我們就會(huì)多加一塊區(qū)域，這塊區(qū)域就是如圖黃色部分，我們?cè)贉p去黃色部分就好了，最后再加上當(dāng)前位置本身就行了。

比如我們想要求 ，則可以通過(guò) 的方式來(lái)實(shí)現(xiàn)。這樣我就可以通過(guò) 的預(yù)處理計(jì)算二維前綴和矩陣(m 和 n 分別為矩陣的長(zhǎng)和寬)，再通過(guò) 的時(shí)間計(jì)算出「任意小矩陣的和」。其底層原理就是上面提到的容斥原理，大家可以通過(guò)畫圖的方式來(lái)感受一下。

如何將二維前綴和轉(zhuǎn)化為一維前綴和

然而實(shí)際上，我們也可不構(gòu)建一個(gè)前綴和數(shù)組，而是直接原地修改。

一維前綴和同樣可以采用這一技巧。

比如我們可以先不考慮行之間的關(guān)聯(lián)，而是預(yù)先計(jì)算出每一行的前綴和。對(duì)于計(jì)算每一行的前綴和就是「一維前綴和」啦。接下來(lái)通過(guò)「固定兩個(gè)列的端點(diǎn)」的方式計(jì)算每一行的區(qū)域和。代碼上，我們可以通過(guò)三層循環(huán)來(lái)實(shí)現(xiàn)， 其中兩層循環(huán)用來(lái)固定列端點(diǎn)，另一層用于枚舉所有行。

其實(shí)也可以反過(guò)來(lái)。即固定行的左右端點(diǎn)并枚舉列，下面的題目會(huì)提到這一點(diǎn)。

代碼表示：

# 預(yù)先構(gòu)建行的前綴和 
for row in matrix: 
    for i in range(n - 1): 
        row[i + 1] += row[i] 

比如矩陣：

1 2 3 4 
5 6 7 8 

則會(huì)變?yōu)椋?/p>

1 3 6 10 
5 11 18 26 

接下來(lái)：

# 固定列的兩個(gè)端點(diǎn)，即枚舉所有列的組合 
for i in range(n): 
    for j in range(i, n): 
        pres = [0] 
        pre = 0 
        # 枚舉所有行 
        for k in range(m): 
            # matrix[k] 其實(shí)已經(jīng)是上一步預(yù)處理的每一行的前綴和了。因此 matrix[k][j] - (matrix[k][i - 1] 就是每一行 [i, j] 的區(qū)域和。 
            pre += matrix[k][j] - (matrix[k][i - 1] if i > 0 else 0) 
            pres.append(pre) 

上面代碼做的事情形象來(lái)看，就是先在水平方向計(jì)算前綴和，然后在豎直方向計(jì)算前綴和，而不是同時(shí)在兩個(gè)方向計(jì)算。

如果把 [i, j] 的區(qū)域和看出是一個(gè)數(shù)的話，問(wèn)題就和一維前綴和一樣了。代碼：

for i in range(n): 
    for j in range(i, n): 
        pres = [0] 
        pre = 0 
        # 枚舉所有行 
        for k in range(m): 
            # 其中 a 為[i, j] 的區(qū)域和 
            pre += a 
            pres.append(pre) 

題目推薦

有了上面的知識(shí)，我們就可以來(lái)解決下面兩道題。雖然下面兩道題的難度都是 hard，不過(guò)總體難度并不高。這兩道題之所以是 hard， 是因?yàn)槠淇疾炝恕覆恢挂粋€(gè)知識(shí)點(diǎn)」。這也是 hard 題目的一種類型，即同時(shí)考察多個(gè)知識(shí)點(diǎn)。

363. 矩形區(qū)域不超過(guò) K 的最大數(shù)值和

題目地址

https://leetcode-cn.com/problems/max-sum-of-rectangle-no-larger-than-k/

題目描述

給定一個(gè)非空二維矩陣 matrix 和一個(gè)整數(shù) k，找到這個(gè)矩陣內(nèi)部不大于 k 的最大矩形和。

示例:

給定一個(gè)非空二維矩陣 matrix 和一個(gè)整數(shù) k，找到這個(gè)矩陣內(nèi)部不大于 k 的最大矩形和。 
 
示例: 
 
輸入: matrix = [[1,0,1],[0,-2,3]], k = 2 
輸出: 2 
解釋: 矩形區(qū)域 [[0, 1], [-2, 3]] 的數(shù)值和是 2，且 2 是不超過(guò) k 的最大數(shù)字（k = 2）。 
 
 
說(shuō)明： 
 
矩陣內(nèi)的矩形區(qū)域面積必須大于 0。 
如果行數(shù)遠(yuǎn)大于列數(shù)，你將如何解答呢？ 

前置知識(shí)

• 二維前綴和
• 二分法

思路

前面提到了由于非負(fù)數(shù)數(shù)組的二維前綴和是一個(gè)非遞減的數(shù)組，因此常常和二分結(jié)合考察。實(shí)際上即使數(shù)組不是非負(fù)的，我們?nèi)匀挥锌赡軜?gòu)建一個(gè)有序的前綴和，從而使用二分，這道題就是一個(gè)例子。

首先我們可以用上面提到的技巧計(jì)算二維數(shù)組的前綴和，這樣我們就可以計(jì)算快速地任意子矩陣的和了。注意到上面我們計(jì)算的 pres 數(shù)組是一個(gè)一維數(shù)組，但矩陣其實(shí)可能為負(fù)數(shù)，因此不滿足單調(diào)性。這里我們可以手動(dòng)維護(hù) pres 單調(diào)遞增，這樣就可以使用二分法在 的時(shí)間求出「以當(dāng)前項(xiàng) i 結(jié)尾的不大于 k 的最大矩形和」，那么答案就是所有的「以任意索引 x 結(jié)尾的不大于 k 的最大矩形和」的最大值。

之所以可以手動(dòng)維護(hù) pres 數(shù)組單調(diào)增也可得到正確結(jié)果的原因是「題目只需要求子矩陣和，而不是求具體的子矩陣」。

代碼上，當(dāng)計(jì)算出 pres 后，我們其實(shí)需要尋找大于等于 pre - k 的最小數(shù) x。這樣矩陣和 pre - x 才能滿足 pre - x <= k，使用最左插入二分模板即可解決。

關(guān)鍵點(diǎn)

• 典型的二維前綴和 + 二分題目

代碼

• 語(yǔ)言支持：Python3

Python3 Code:

class Solution: 
    def maxSumSubmatrix(self, matrix: List[List[int]], K: int) -> int: 
        m, n = len(matrix), len(matrix[0]) 
        ans = float("-inf") 
        for row in matrix: 
            for i in range(n - 1): 
                row[i + 1] += row[i] 
 
        for i in range(n): 
            for j in range(i, n): 
                pres = [0] 
                pre = 0 
                for k in range(m): 
                    pre += matrix[k][j] - (matrix[k][i - 1] if i > 0 else 0) 
                    # 尋找大于等于 pre - k 的最小數(shù)，且這個(gè)數(shù)不能比 pre 大。比如 pre = 10， k = 3，就要找大于等于 7 的最小數(shù)，這個(gè)數(shù)不能大于 10。 
                    # 為了達(dá)到這個(gè)目的，可以使用 bisect_left 來(lái)完成。（使用 bisect_right 不包含等號(hào)） 
                    idx = bisect.bisect_left(pres, pre - K) 
                    # 如果 i == len(pre) 表示 pres 中的數(shù)都小于 pre - k，也就是說(shuō)無(wú)解 
                    if idx < len(pres): 
                        # 由 bisect_left 性質(zhì)可知 pre - pres[i] >= 0 
                        ans = max(ans, pre - pres[idx]) 
                    idx = bisect.bisect_left(pres, pre) 
                    pres[idx:idx] = [pre] 
                    # 或者將上面兩行代碼替換為 bisect.insort(pres, pre) 
        return -1 if ans == float("-inf") else ans 

「復(fù)雜度分析」

令 n 為數(shù)組長(zhǎng)度。

• 時(shí)間復(fù)雜度：
• 空間復(fù)雜度：

題目給了一個(gè) follow up：如果行數(shù)遠(yuǎn)大于列數(shù)，你將如何解答呢?實(shí)際上，如果行數(shù)遠(yuǎn)大于列數(shù)，由復(fù)雜度分析可知空間復(fù)雜度會(huì)很高。我們可以將行列兌換，這樣空間復(fù)雜度是 。換句話說(shuō)，我們「可以通過(guò)行列的調(diào)換」做到空間復(fù)雜度為 。

1074. 元素和為目標(biāo)值的子矩陣數(shù)量

題目地址

https://leetcode-cn.com/problems/number-of-submatrices-that-sum-to-target/

題目描述

給出矩陣 matrix 和目標(biāo)值 target，返回元素總和等于目標(biāo)值的非空子矩陣的數(shù)量。 
 
子矩陣 x1, y1, x2, y2 是滿足 x1 <= x <= x2 且 y1 <= y <= y2 的所有單元 matrix[x][y] 的集合。 
 
如果 (x1, y1, x2, y2) 和 (x1', y1', x2', y2') 兩個(gè)子矩陣中部分坐標(biāo)不同（如：x1 != x1'），那么這兩個(gè)子矩陣也不同。 
 
  
 
示例 1： 
 
輸入：matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0 
輸出：4 
解釋：四個(gè)只含 0 的 1x1 子矩陣。 
 
 
示例 2： 
 
輸入：matrix = [[1,-1],[-1,1]], target = 0 
輸出：5 
解釋：兩個(gè) 1x2 子矩陣，加上兩個(gè) 2x1 子矩陣，再加上一個(gè) 2x2 子矩陣。 
 
 
  
 
提示： 
 
1 <= matrix.length <= 300 
1 <= matrix[0].length <= 300 
-1000 <= matrix[i] <= 1000 
-10^8 <= target <= 10^8 

前置知識(shí)

• 二維前綴和

思路

和上面題目類似。不過(guò)這道題是求子矩陣和剛好等于某個(gè)目標(biāo)值的「數(shù)目」。

我們不妨先對(duì)問(wèn)題進(jìn)行簡(jiǎn)化。比如題目要求的是一維數(shù)組中，子數(shù)組(連續(xù))的和等于目標(biāo)值 target 的數(shù)目。我們?cè)撊绾巫?

這很容易，我們只需要：

• 邊遍歷邊計(jì)算前綴和。
• 比如當(dāng)前的前綴和是 cur，那么我們要找的前綴和 x 應(yīng)該滿足 cur - x = target，因?yàn)檫@樣當(dāng)前位置和 x 的之間的子數(shù)組和才是 target。即我們需要找前綴和為 cur - target 「的數(shù)目」。這提示我們使用哈希表記錄每一種前綴和出現(xiàn)的次數(shù)。

由于僅僅是求數(shù)目，不涉及到求具體的子矩陣信息，因此使用類似上面的解法求出二維前綴和。接下來(lái)，使用和一維前綴和同樣的方法即可求出答案。

關(guān)鍵點(diǎn)

主要考察一維前綴和到二維前綴和的過(guò)渡是否掌握

代碼

• 語(yǔ)言支持：Python3

Python3 Code:

class Solution: 
    def numSubmatrixSumTarget(self, matrix, target): 
        m, n = len(matrix), len(matrix[0]) 
        for row in matrix: 
            for i in range(n - 1): 
                row[i + 1] += row[i] 
        ans = 0 
        for i in range(n): 
            for j in range(i, n): 
                c = collections.defaultdict(int) 
                cur, c[0] = 0, 1 
                for k in range(m): 
                    cur += matrix[k][j] - (matrix[k][i - 1] if i > 0 else 0) 
                    ans += c[cur - target] 
                    c[cur] += 1 
        return ans 

「復(fù)雜度分析」

• 時(shí)間復(fù)雜度：
• 空間復(fù)雜度：

和上面一樣，我們可以將行列對(duì)換，這樣空間復(fù)雜度是 。換句話說(shuō)，我們「可以通過(guò)行列的調(diào)換」做到空間復(fù)雜度為 。

本文轉(zhuǎn)載自微信公眾號(hào)「力扣加加」，可以通過(guò)以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系力扣加加公眾號(hào)。