最近LeetCodeに時間通り出てないなぁ。
https://leetcode.com/contest/weekly-contest-139/problems/number-of-submatrices-that-sum-to-target/
問題
行列Aと値Tが与えられる。
Aの部分行列のうち、総和がTとなるのは何通りか。
解法
先に累積和で連続する列の和をO(1)でとれるようにしておく。
列の左端と右端を総当たりすると、あとは行を走査していくと、よくある数列のsubsequenceで総和がある定数と一致するものを探す問題になる。
計算量だとO(N^3logN)かな。
ll S[303][303]; class Solution { public: int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) { int H=matrix.size(); int W=matrix[0].size(); int x,y; ZERO(S); FOR(y,H) FOR(x,W) S[y][x+1]=S[y][x]+matrix[y][x]; ll ret=0; for(int x1=0;x1<W;x1++) { for(int x2=x1;x2<W;x2++) { map<ll,int> num; ll sum=0; num[0]=1; FOR(y,H) { sum+=S[y][x2+1]-S[y][x1]; ret+=num[sum-target]; num[sum]++; } } } return ret; } };
まとめ
これ系、一度見たことあるとすぐ思いつくけど初見だと大変だよね。