如果矩陣只包含大於等於0的值，那麼在1D情況下有一個線性時間解，可以在2D情況下將其擴展爲立方時間解。
對於1D的情況，您可以從左到右進行一次遍歷，在整個數組上滑動一個窗口，隨着時間的推移或縮小，使得間隔中包含的數字總是至少爲k如果這是不可能的，則退出循環）。
最初，設置結合的間隔與所述第一元件的左手食指，並結合至-1正確的索引，則在一個循環：
- 遞增1結合的右側，然後不斷遞增直到達到區間內的值總和爲> k或數組的末尾。
- 遞增左邊界以儘可能小地縮小間隔，而不讓數值總和小於或等於k。
- 如果結果是一個有效的時間間隔（意思是第一步沒有找到一個有效的時間間隔到達數組的末尾），那麼比較它到目前爲止的最小值並在必要時進行更新。
如果允許負值，這不起作用，因爲在第二步中，您需要能夠假設收縮間隔總是導致較小的總和，所以當總和低於k時，您知道這是給定間隔端點的最小可能值。
對於2D情況，您可以遍歷所有可能的子矩陣高度，以及遍歷給定高度的每個可能的起始行，並對每行執行此水平掃描。
在僞碼：
假設有一個功能rectangle_sum(x, y, a, b)，從（X，Y）返回值的總和到（A，B），其中包括與運行在O（1）時所使用的求和麪積表。
for(height = 1; height <= M; height++) // iterate over submatrix heights
{
for(row = 0; row <= (M-h); row++) // iterate over all rows
{
start = 0; end = -1; // initialize interval
while(end < N) // iterate across the row
{
valid_interval = false;
// increment end until the interval sums to > k:
while(end < (N-1))
{
end = end + 1;
if(rectangle_sum(start, row, end, row + height) > k)
{
valid_interval = true;
break;
}
}
if(!valid_interval)
break;
// shrink interval by incrementing start:
while((start < end) &&
rectangle_sum(start+1, row, end, row + height) > k))
start = start + 1;
compare (start, row), (end, row + height) with current smallest
submatrix and make it the new current if it is smaller
}
}
}
矩陣是否可以包含負值？ （我知道你說的整數，但只是檢查） – samgak
哦...對了，我忘了提及它，只有intigers> = 0 –