如何在Java中发现子数组在二维数组中是否有特定的和？

Question

但这涉及到寻找一个具有最大和的子数组，而不是已经给出的和。

So if this the given array.

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

And if the given sum is 19, then it should return this window

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

And if the given sum is 23, then it should return this window

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
    

我怎样才能有效地找到这个？这里可以用动态规划吗？请帮帮我。

Answer 1

使用相同的原理，但对于一个更简单的问题。首先，我预先计算数组每一列的累计和，即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));
                }
            }
        }
    }
}