如何查找子阵列在Java中的2D数组中是否有特定的总和？ [英] How to find if a subarray has a specific sum inside a 2D array in Java ?
问题描述
我试图通过比较源图像和图案图像中存在的像素的平均颜色来解决图像匹配问题。我已经将这个问题简化为子数组求和问题，但无法找到解决问题的方法。
I am trying to solve a Image matching problem by comparing the average color of pixels present in both the source and pattern image. I have reduced this problem to a sub array sum problem, but cannot figure out a way to solve it.
假设我有一个带有所有正整数的二维阵列ARR。我有一个数字x（这是小图案图像中存在的像素颜色的平均值）。我只需要在ARR中找到具有精确和x的任何子阵列。我发现了一个类似的问题，可以通过动态编程来解决。
Lets say i have a 2D array ARR with all positive integers. I have a number x( which is the average of the pixel colors present in a small pattern image). I just need to find any subarray in ARR which has the exact sum x. I found a similar problem which could be solved with Dynamic programming here.
http://www.geeksforgeeks.org/dynamic-programming-set-27-max-sum-rectangle-in-a-2d-matrix/
但这涉及到找到最大金额的子阵列，而不是已经给出的总和。
But that talks about finding a subarray with maximum sum and not the sum which was already given.
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
我怎样才能有效地找到这个？可以在这里使用动态编程吗？请帮帮我。
How can i find this efficiently ? Can Dynamic Programming be used here ? Please help me out here.
推荐答案
使用相同的原理，但是对于一个更简单的问题。首先，我预先计算数组的每个列的累积和，即A [i] [j] + = A [i-1] [j]。
Using the same principle, but for a simpler problem. First, I precompute the cumulative sum for each column of the array, i.e., A[i][j] += A[i-1][j].
然后，对于每对开始/结束行（i1，i2），我将它们视为单个数组B [j]，这意味着B [j] = A [i2] [j] - A [I1-1] [j]的。然后，我们需要找到具有精确总和的子阵列。由于数组仅由正数组成，我可以在O（n）中找到它。
Then, for each pair of start/end rows (i1, i2), I treat them as a single array B[j], that means B[j] = A[i2][j] - A[i1-1][j]. Then, we need to find the subarray with the exact sum. As the array is composed only by positive numbers, I can find it in O(n).
总的来说，这个算法是O（n ^ 3）。
Overall, this algorithm is O(n^3).
对于您提供的值，我能够找到一些附加数组：
For the values you supplied, I was able to find some additionals arrays:
对于target = 19：
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)
目标= 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));
}
}
}
}
}
这篇关于如何查找子阵列在Java中的2D数组中是否有特定的总和？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
