Number of Submatrices That Sum to Target LeetCode solution in Java

1
class Solution {
2
  public int numSubmatrixSumTarget(int[][] matrix, int target) {
3
    int m = matrix.length, n = matrix[0].length;
4

5
    int[] summedArray = new int[n];
6
    int ans = 0;
7
    for (int i = 0; i < m; i++) { // starting row
8
      Arrays.fill(summedArray, 0);
9
      for (int j = i; j < m; j++) { // ending row
10
        for (int k = 0; k < n; k++) { // column
11
          summedArray[k] += matrix[j][k];
12
        }
13
        ans += subarraySum(summedArray, target);
14
      }
15
    }
16
    return ans;
17
  }
18

19
  public int subarraySum(int[] nums, int k) {
20
    // map<sum, freq>
21
    Map<Integer, Integer> map = new HashMap<>();
22
    int count = 0;
23
    map.put(0, 1);
24
    int sum = 0;
25
    for (int num : nums) {
26
      sum += num;
27
      int diff = sum - k;
28
      if (map.containsKey(diff)) {
29
        count += map.get(diff);
30
      }
31
      map.put(sum, map.getOrDefault(sum, 0) + 1);
32
    }
33
    return count;
34
  }
35
}