LeetCode Weekly Contest 139 : 1074. Number of Submatrices That Sum to Target

最近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;
        
    }
};

まとめ

これ系、一度見たことあるとすぐ思いつくけど初見だと大変だよね。