Re: [閒聊] 每日LeetCode

[oin1104 (是oin的說)]

今天是問 在一個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;



    }
};





--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.162.0.147 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1706432707.A.3C0.html
推 wu10200512: ==
→ wu10200512: 4層迴圈也能過ㄛ 好狠
→ oin1104: = =
→ oin1104: 對ㄚ 好爽
→ oin1104: 而且我還beat 66% 其他人是在幹三小
→ oin1104: 好像是因為這個才100*100 所以頂多10000*10000 穩的
→ SecondRun: 大師