如何检查数组的所有可能矩形的和

Question

假设有一个二维数组A(n X n)，其中所有元素都为0或1。另外有一个整数K。我们的任务是找到A中所有可能的“矩形”，其包含总和为K的元素数量。

To give an example , if A = 
0 0 1 0 
1 0 0 1
1 1 1 1
1 0 0 1   and k=3 ,

0 0 1 0
1 0 0 1  holds the property ,

1 1 1 holds the property ,

  1 1 1 holds the property ,

0 0 
1 0 
1 1 holds the property ,

1 1
1 0  holds the property ,

    1 1
    0 1  holds the property ,

1
1
1  holds the property

1
1
1 holds the property 

除非我漏掉了什么，否则这个例子的答案应该是8。

换句话说，我们需要检查矩阵A中所有可能的矩形，以查看它们元素的总和是否为K。有没有一种比O(n^2 * k^2)更快的方法？

- user3697730

---

检查所有矩形的简单算法不需要 O(n^4) 的时间吗？ - Vincent van der Weele

Answer 1

我认为情况比你计算的更糟。我发现总共有14个带有三个1（绿色方块）的矩形。我使用的方法是将数组中的每个{行，列}位置作为矩形左上角，然后考虑每种可能的宽度和高度组合。

由于宽度和高度不受k的限制（至少不是直接受限），搜索时间复杂度为O（n^4）。当然，对于任何给定的{row，column，width}，当高度使总和大于k时，搜索就会结束。但这并不改变最坏情况下的时间复杂度。

右下角的三个起始点不需要考虑，因为从这些位置开始无法构造包含k个1的矩形。但同样，这并不改变时间复杂度。

注：我知道这更像是一条评论而不是答案。但是，它无法适应评论，并且我认为对OP仍然有用。在完全理解问题之前，您无法解决问题。

- user3386109

Answer 2

你可以通过O(n^3)的复杂度完成此任务。

首先需要注意使用积分图表(summed area table)，在O(n^2)的预处理时间内就能够计算任何矩形的和，从而实现O(1)的时间内对矩阵中每一列的求和。

虽然针对此问题我们只需要对列进行求和，但这种通用方法值得掌握。

接下来，对于每个开始行和结束行的组合，你可以通过线性扫描矩阵，采用双指针法或者简单地存储前一个和来计算解的数量。

以下是Python示例代码（找到了14个解决方案）：

from collections import defaultdict
A=[[0, 0, 1, 0],
[1, 0, 0, 1],
[1, 1, 1, 1],
[1, 0, 0, 1]]
k=3

h=len(A)
w=len(A[0])

C=[ [0]*w for i in range(h+1)]
for x in range(w):
    for y in range(1,h+1):
        C[y][x] = C[y-1][x] + A[y-1][x]
# C[y][x] contains sum of all values A[y2][x] with y2<y

count=0
for start_row in range(h):
    for end_row in range(start_row,h):
        D=defaultdict(int) # Key is sum of columns from start to here, value is count
        D[0]=1
        t=0 # Sum of all A[y][x] for x <= col, start_row<=y<=end_row
        for x in range(w):
            t+=C[end_row+1][x] - C[start_row][x]
            count += D[t-k]
            D[t] += 1
print count

- Peter de Rivaz