如何在 Java 中查找 2D 数组中的子数组是否具有特定的和？

我试图通过比较源图像和图案图像中存在的像素的平均颜色来解决图像匹配问题。我已将这个问题简化为子数组求和问题，但无法找到解决方法。

假设我有一个包含所有正整数的二维数组 ARR。我有一个数字 x（它是小图案图像中存在的像素颜色的平均值）。我只需要在 ARR 中找到具有精确总和 x 的任何子数组。我发现了一个类似的问题，可以通过动态编程来解决这里。

http://www.geeksforgeeks.org/dynamic-programming-set-27-max-sum-rectangle-in-a-2d-matrix/ http://www.geeksforgeeks.org/dynamic-programming-set-27-max-sum-rectangle-in-a-2d-matrix/

但这是关于寻找一个子数组最大总和而不是已经给出的金额。

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
    
  

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

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