-
-
Notifications
You must be signed in to change notification settings - Fork 299
/
1074.java
45 lines (37 loc) · 1.32 KB
/
1074.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
__________________________________________________________________________________________________
class Solution {
public int numSubmatrixSumTarget(int[][] matrix, int target) {
int m = matrix.length;
int n = matrix[0].length;
int[] temp = new int[m];
int ans=0;
for (int left = 0;left<n;left++) {
Arrays.fill(temp,0);
for (int right=left;right<n;right++) {
for (int i=0;i<m;i++) {
temp[i]+=matrix[i][right];
}
ans+= subCount(temp,target);
}
}
return ans;
}
private int subCount(int[] temp,int target) {
HashMap<Integer, Integer> prevSum = new HashMap<>();
int res = 0;
int currentSum = 0;
for (int t : temp) {
currentSum += t;
if (currentSum == target) {
res++;
}
if (prevSum.containsKey(currentSum - target)) {
res += prevSum.get(currentSum - target);
}
prevSum.merge(currentSum, 1, (a, b) -> a + b);
}
return res;
}
}
__________________________________________________________________________________________________
__________________________________________________________________________________________________