如何找到一個子數組是否在Java中的二維數組內有特定的總和？

Question

我試圖通過比較源圖案和圖案圖像中存在的像素的平均顏色來解決圖像匹配問題。我已經將這個問題簡化爲一個子數組求和的問題，但無法找到解決這個問題的方法。

可以說我有一個二維數組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 

我該如何有效地找到它？動態編程可以在這裏使用嗎？請幫我在這裏。

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）。

對於您所提供的價值，我能找到一些additionals陣列：

對於目標= 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)); 
       } 
      } 
     } 
    } 
}