Sub Matrix Sum

TAG : Subarray + 数据压缩

code

class Solution {
public:
    /**
     * @param matrix an integer matrix
     * @return the coordinate of the left-up and right-down number
     */
    vector<vector<int>> submatrixSum(vector<vector<int>>& matrix) {
        // Write your code here
        vector<vector<int>> ret;
        int m = matrix.size();
        if(m == 0)
        {
            return ret;
        }
        int n = matrix[0].size();

        // 1, make prefix sum matrix;

        vector<vector<int>> prefix_matrix;

        for(int i = 0; i<m+1; i++)
        {
            vector<int> tmp(n, 0);
            prefix_matrix.push_back(tmp);
        }

        for(int i = 1; i<m+1; i++)
        {
            for(int j = 0; j<n; j++)
            {
                prefix_matrix[i][j] = matrix[i-1][j] + prefix_matrix[i-1][j];
                //cout<<prefix_matrix[i][j]<<" ";
            }
            //cout<<endl;
        }


        // 2, select two rows
        for(int i = 0; i<m; i++)
        {
            for(int j = i; j<m; j++)
            {
                // 3, make current vector
                vector<int> cur(n, 0);
                for(int r = 0; r < n; r++)
                {
                    cur[r] = prefix_matrix[j+1][r] - prefix_matrix[i][r];

                    //cout<<cur[r]<<" ";

                }
                cout<<endl;
                // 4, use subarray sum idea to solve the problem

                map<int, int> hash;
                hash[0] = 0;
                int sum = 0;
                for(int r = 0; r<n; r++)
                {
                    sum += cur[r];
                    if(hash.find(sum) != hash.end())
                    {
                        //cout<<hash[sum]<<endl;
                        vector<int> lt;
                        lt.push_back(i);
                        lt.push_back(hash[sum]);
                        //cout<<i<<" "<<hash[sum]<<endl;

                        vector<int> rb;
                        rb.push_back(j);
                        rb.push_back(r);
                        //cout<<j<<" "<<r<<endl;

                        ret.push_back(lt);
                        ret.push_back(rb);
                        return ret;
                    }
                    hash[sum] = r+1;
                }
            }
        }

        return ret;

    }
};