考虑这个更简单的问题：
给定一个大小为 N 的向量，仅包含值 1 和 0，找到一个恰好包含 k 个值 1 的子序列。
令A为给定向量 和S[i] = A[1] + A[2] + A[3] + ... + A[i]，表示子序列 中有多少个 1 A[1..i]。
对于每一个，我们都对这样的i存在感兴趣。j <= iS[i] - S[j-1] == k
O(n)我们可以使用以下关系通过哈希表找到它：
S[i] - S[j-1] == k => S[j-1] = S[i] - k
let H = an empty hash table
for i = 1 to N do
if H.Contains (S[i] - k) then your sequence ends at i
else
H.Add(S[i])
现在我们可以用它来解决您给定的问题O(N^3)：对于给定矩阵中的每个行序列（存在O(N^2)行序列），考虑该序列来表示向量并对其应用先前的算法。在矩阵情况下，的计算S有点困难，但并不难算出来。如果您需要更多详细信息，请告诉我。
更新：
以下是该算法如何在以下矩阵上工作，假设k = 12：
0 1 1 1 1 0
0 1 1 1 1 0
0 1 1 1 1 0
单独考虑第一行：
0 1 1 1 1 0
将其视为向量0 1 1 1 1 0并对其应用更简单问题的算法：我们发现没有子序列加起来等于 12，因此我们继续。
考虑前两行：
0 1 1 1 1 0
0 1 1 1 1 0
将它们视为向量0+0 1+1 1+1 1+1 1+1 0+0 = 0 2 2 2 2 0并对其应用更简单问题的算法：同样，没有子序列加起来等于 12，所以继续。
考虑前三行：
0 1 1 1 1 0
0 1 1 1 1 0
0 1 1 1 1 0
将它们视为向量0 3 3 3 3 0并对其应用更简单问题的算法：我们发现从位置 2 开始到位置 5 结束的序列就是解。由此我们可以通过简单的记账得到整个矩形。