Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
1.0 kB
0
Indexable
Never
class Solution {
public:
    int numSubmatrixSumTarget(vector<vector<int>>& mat, int target) {
        int r=mat.size(), c=mat[0].size();
        vector<vector<int>>pre(r,vector<int>(c,0));
        pre[0][0]=mat[0][0];
        for(int i=0;i<r;i++){
            for(int j=0;j<c;j++){
                pre[i][j]=mat[i][j];
                if(i>0) pre[i][j]+=pre[i-1][j];
                if(j>0) pre[i][j]+=pre[i][j-1];
                if(i>0 && j>0) pre[i][j]-=pre[i-1][j-1];
            }
        }
        int res=0;
        for(int I=0;I<r;I++){
            for(int J=0;J<c;J++){
                for(int i=I;i<r;i++){
                    for(int j=J;j<c;j++){
                        int sum=pre[i][j];
                        if(I>0) sum-=pre[I-1][j];
                        if(J>0) sum-=pre[i][J-1];
                        if(I>0 && J>0) sum+=pre[I-1][J-1];
                        if(sum==target) res++;
                    }
                }
            }
        }
        return res;
    }
};
Leave a Comment