Simple And Easy To Understand || 2D converted to 1D || Subarrray sum equal to K
Intuition \nTraverse and calcuate prefix sum\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the
# Intuition \nTraverse and calcuate prefix sum\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nJust stored the 2D vector sum into 1D vector and applied subarray sum \n\nFor example let\'s try for \n\nmatrix=[[0 , 1, 0],[1, 1, 1], [0, 1, 0]]  Target=3\n\nfor i=0\nIn 1st loop our vector will be (0,1,0) check for sum 3 no subarray \nnow next loop vector will become (1,2,1) check for 3 we will get **two** subarray (1,2) and (2,1) \nnow next loop vector will become (1,3,1) check for 3 we will get **one** subarray (3)\n\nfor i=1\nIn 1st loop our vector will be (1,1,1) check for sum 3 **one** subarray (1,1,1)\nnow next loop vector will become (1,2,1) check for 3 we will **two** subarray (1,2) and (2,1)\n\nfor i=2\nIn 1st loop our vector will be (0,1,0) check for sum 3 no subarray\n\n\nFinally the answer is **6** \n\nIn these way we can convert 2D array in 1D an apply subarray sum equals K method\n\n\n\n# Complexity\n- Time complexity:O(n * n * n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int subarraysum(vector<int>& nums, int k)\n    {\n        unordered_map<int,int> m;\n        m[0]=1;\n        int curr=0,ans=0;\n\n        for(auto &val:nums)\n        {\n            curr+=val;\n            if(m.find(curr-k)!=m.end())\n            {\n                ans+=m[curr-k];\n            }\n            m[curr]++;\n        }\n\n        return ans;\n    }\n    int numSubmatrixSumTarget(vector<vector<int>>& mat, int target) {\n        int ans=0;\n\n        for(int i=0;i<mat.size();i++)\n        {\n            vector<int> sum(mat[0].size(),0);\n            for(int j=i;j<mat.size();j++)\n            {\n               for(int k=0;k<mat[0].size();k++)\n               {\n                  sum[k]+=mat[j][k];\n               }\n               \n               ans+=subarraysum(sum,target);\n            }\n        }\n\n        return ans;\n    }\n};\n```
['Prefix Sum', 'C++']