今天是問 在一個2d的陣列裡面
有多少個子陣列加起來==target
我用prefix sum做的
然後我剛剛看
好像可以用hashmap加上去做
好扯喔
class Solution {
public:
int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target)
{
int ans = 0;
vector<vector<int>> summat ;
summat = matrix;
int n = matrix[0].size();
int m = matrix.size();
for(int i = 1 ; i < n ; i ++)
{
summat[0][i] += summat[0][i-1];
}
for(int i = 1 ; i < m ; i ++)
{
summat[i][0] += summat[i-1][0];
}
for(int i = 1 ; i < m ; i ++)
{
for(int j = 1 ; j < n ; j ++)
{
summat[i][j] = summat[i][j] + summat[i-1][j] + summat[i][j-1] -
summat[i-1][j-1];
}
}
for(int na = 0 ; na < n ; na ++)
{
for(int ma = 0 ; ma < m ; ma ++)
{
for(int nb = na ; nb < n ; nb ++)
{
for(int mb = ma ; mb < m ; mb ++)
{
int k = 0 ;
if((na > 0)&&(ma > 0))
{
k = summat[mb][nb] - summat[mb][na-1] - summat[ma-1]
[nb] + summat[ma-1][na-1];
}
else if(na > 0)
{
k = summat[mb][nb] - summat[mb][na-1] ;
}
else if(ma > 0)
{
k = summat[mb][nb] - summat[ma-1][nb] ;
}
else
{
k = summat[mb][nb] ;
}
if(k == target) ans ++;
}
}
}
}
return ans;
}
};