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

Question

我试图通过比较源图像和模式图像中存在的像素的平均颜色来解决图像匹配问题。我已经把这个问题简化为一个子数组求和问题，但是我想不出一个办法来解决。

假设我有一个2D数组ARR，所有的都是正整数。我有一个数字x(它是小图案图像中出现的像素颜色的平均值)。我只需要在ARR中找到具有精确和x的任何子数组。我发现了一个类似的问题，可以用动态规划在这里解决。

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

但是这里说的是找到一个和最大的子数组，而不是已经给出的和

<>之前如果这是给定的数组。3 4 8 9 32 10 4 2 18 1 4 8 03 5 2 12 38 1 1 2 2如果给定的和是19，那么它应该返回这个窗口3 4 8 9 32 10 4 28 1 4 8 03 5 2 12 38 1 1 2 2如果给定的和是23，那么它应该返回这个窗口3 3 2 4 2 18 1 1 03 5 2 12 38 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)。

对于您提供的值，我能够找到一些额外的数组:

For target = 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)

target = 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));
                }
            }
        }
    }
}