让我们假设我们有一个二维数组 A (n X n)。 A 的所有元素要么是 O 要么是 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) 更快的方法?
最佳答案
您可以在 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
关于arrays - 如何检查数组所有可能矩形的总和,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40321927/