• Leetcode 3070. Count Submatrices with Top-Left Element and Sum Less Than k
  • 1. 解題思路
  • 2. 代碼實現

• 題目鏈接：3070. Count Submatrices with Top-Left Element and Sum Less Than k

1. 解題思路

這一題就是一個二維的累積數組的問題，我們直接求一下累積數組然后找一下滿足條件的矩陣就行了。

另外，由于只需要尋找和不大于k的矩陣，因此我們可以在和超過k時提前跳出來進行剪枝，從而優化執行效率。

2. 代碼實現

給出python代碼實現如下：

class Solution:def countSubmatrices(self, grid: List[List[int]], k: int) -> int:n, m = len(grid), len(grid[0])s = [[0 for _ in range(m+1)] for _ in range(n+1)]ans = 0for i in range(n):for j in range(m):s[i+1][j+1] = grid[i][j] + s[i+1][j] + s[i][j+1] - s[i][j]if s[i+1][j+1] <= k:ans += 1else:breakreturn ans

提交代碼評測得到：耗時1591ms，占用內存65.8MB。