aboutsummaryrefslogtreecommitdiff
path: root/other/number_submatrices_sum_target.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'other/number_submatrices_sum_target.cpp')
-rw-r--r--other/number_submatrices_sum_target.cpp24
1 files changed, 24 insertions, 0 deletions
diff --git a/other/number_submatrices_sum_target.cpp b/other/number_submatrices_sum_target.cpp
new file mode 100644
index 0000000..db5a84f
--- /dev/null
+++ b/other/number_submatrices_sum_target.cpp
@@ -0,0 +1,24 @@
+#include "leetcode.h"
+
+class Solution {
+public:
+ int numSubmatrixSumTarget(vector<vector<int>> &matrix, int target) {
+ int xLen = matrix[0].size(), yLen = matrix.size(), ans = 0;
+ unordered_map<int, int> res;
+ for (int i = 0; i < yLen; i++)
+ for (int j = 1; j < xLen; j++)
+ matrix[i][j] += matrix[i][j - 1];
+ for (int j = 0; j < xLen; j++)
+ for (int k = j; k < xLen; k++) {
+ res.clear();
+ res[0] = 1;
+ int cSum = 0;
+ for (int i = 0; i < yLen; i++) {
+ cSum += matrix[i][k] - (j ? matrix[i][j - 1] : 0);
+ ans += res.find(cSum - target) != res.end() ? res[cSum - target] : 0;
+ res[cSum]++;
+ }
+ }
+ return ans;
+ }
+};