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

发布时间：2020-12-14 06:08:39 所属栏目：Java 来源：网络整理

导读：我试图通过比较源图像和图案图像中存在的像素的平均颜色来解决图像匹配问题.我已经将这个问题简化为子数组求和问题,但无法找到解决问题的方法. 假设我有一个带有所有正整数的二维阵列ARR.我有一个数字x(这是小图案图像中存在的像素颜色的平均值).我只需要在A

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

假设我有一个带有所有正整数的二维阵列ARR.我有一个数字x(这是小图案图像中存在的像素颜色的平均值).我只需要在ARR中找到具有精确和x的任何子阵列.我发现了类似的问题,可以通过动态编程来解决.

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

我怎样才能有效地找到它？可以在这里使用动态编程吗？请帮帮我.

最佳答案

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

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

对于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) 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,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,2,1},{8,1,0},{3,5,12,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


                        （编辑：李大同）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!