同じ原理を使用しますが、より単純な問題に使用します。まず、配列の各列の累積合計を事前に計算します。つまり、A[i][j] += A[i-1][j] です。
次に、開始行と終了行の各ペア (i1、i2) を単一の配列 B[j] として扱います。つまり、B[j] = A[i2][j] - A[i1-1][ j]. 次に、正確な合計で部分配列を見つける必要があります。配列は正の数だけで構成されているため、O(n) で見つけることができます。
全体として、このアルゴリズムは O(n^3) です。
あなたが提供した値について、いくつかの追加配列を見つけることができました:
ターゲット = 19 の場合:
Found between (0,0) and (1,1)
Found between (0,3) and (2,4)
Found between (0,2) and (4,2)
Found between (1,1) and (2,2)
Found between (1,2) and (2,4)
Found between (2,0) and (4,0)
Found between (3,3) and (4,5)
ターゲット = 23:
Found between (0,2) and (1,3)
Found between (0,3) and (2,4)
Found between (2,0) and (3,2)
Found between (2,3) and (3,4)
Found between (3,1) and (4,4)
私が使用したコード:
public static void main(String[] args) {
int[][] A = {
{3, 4, 8, 9, 3},
{2, 10, 4, 2, 1},
{8, 1, 4, 8, 0},
{3, 5, 2, 12, 3},
{8, 1, 1, 2, 2},
};
int target = 19;
for (int i = 1; i < A.length; i++)
for (int j = 0; j < A[i].length; j++)
A[i][j] += A[i - 1][j];
for (int i1 = 0; i1 < A.length; i1++) {
for (int i2 = i1 + 1; i2 < A.length; i2++) {
int j1=0, j2=0, s=0;
while(j2<A[i1].length) {
while(s<target && j2<A[i1].length) {
s += A[i2][j2] - (i1 > 0 ? A[i1-1][j2] : 0);
j2++;
if (s==target)
System.out.println(String.format("Found between (%d,%d) and (%d,%d)", i1, j1, i2, j2-1));
}
while(s>=target) {
s -= A[i2][j1] - (i1 > 0 ? A[i1-1][j1] : 0);
j1++;
if (s==target)
System.out.println(String.format("Found between (%d,%d) and (%d,%d)", i1, j1, i2, j2));
}
}
}
}
}