[C++] O(n^3) Simple 1D Subarray target sum applied to 2D array
Explaination:\nCheck out how to solve for 1D array 560. Subarray Sum Equals K in O(n) time.\n\nThe solution for 1D array uses running prefix sum.\n We know that
**Explaination:**\nCheck out how to solve for 1D array `560. Subarray Sum Equals K` in O(n) time.\n\nThe solution for 1D array uses running prefix sum.\n* We know that to get sum of a subarray `[j,i]` we can calculate using `SUM[0,i] - SUM [0,j-1]`.\n* If this calculation = target then we have a subarray who\'s sum equals target and ends at `i`.\n* Hence at any point `i` we need to find number of occurence of `runningSum - target` since `x + target = runningSum`.\n* We start moving from 1st element to the last and keep adding the value to running sum.\n* We also keep a hash map maintaining number of such sums occured.\n* Thus at any point `i` we have sums from [0,i) stored in hashmap where `i` ranges from `0` to `i` excluding `i`. eg: at `i=3`, we have `SUM[0,0`] , `SUM[0,1]` and `SUM[0,2]`.\n* At each index `i` we can then query the hashmap to find out number of occurences of `runningSum-target` to get number of subarrays ending at `i`.\n\nNow since we know how to find number of subarrays who\'s sum equals target for 1D array.\nWe can convert a 2D matrix of values to 1D matrix whose values equal to that of 2D. Such that they have combination of all rows and apply the same technique.\neg: [[1,2,3,4,5],[2,6,7,8,9]]\n\nWe can break this down to 1 2x5 matrix and 2 1x5 matrix\nThus the 1D value matrices are:\n* We start row wise\n* 1st 1x5 matrix is matrix[0] itself [1,2,3,4,5].\n* We then add second row to previous 1D matrix and get [3,8,10,12,14].\n* We then move on to make matrices with 2nd row of the original matrix as their first row.\n* Since 2nd row is the last we end up with last 1D matrix of [2,6,7,8,9].\n\nWe use the same technique for each 1D matrix created in above steps and keep adding the result for these individual 1D arrays and return that as the result in the end.\n\nIf you notice in the case of 1D array you get results for subarrays of all lengths starting from any point.\nso you are checking rectangles of 1x1, 1x2, 1x3 ..... upto length.\nWhen you apply this to a 2D->1D array at each `i` you are checking rectangles of all sizes starting from `i`.\nwhich looks like ( (1x1, 1x2 ...upto length of row then 2x1, 2x2 ...upto length of a row) .... upto length of columns) for each row in original matrix as their 1st row, hence the result includes all combinations of submatrices.\n\n**Note:** You can make this a little bit faster by sacrificing space and precalculating all prefix sums in the 2D matrix and storing them as in `304. Range Sum Query 2D - Immutable` so that we have a constant lookup for calculating sums, this way we avoid recalculating sums of overlapping rows.\n\n**Solution:**\n```c++\nclass Solution {\npublic:\n    int result=0,target;\n    unordered_map<int,int> map;\n    void get_result(vector<int>& nums)                          //Get number of subarrays that sum to target.\n    {\n        int sum=0;\n        map.clear();\n        map[0]++;\n        for(int &i:nums)\n        {\n            sum+=i;\n            result+=map[sum-target];       //get number of subarrays who\'s sum equals target and end at i and add result to global result.\n            map[sum]++;                    //Add the occurence of running sum to map.\n        }\n    }\n    int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) \n    {\n        this->target=target;\n        vector<int> row(matrix[0].size());\n        for(int i=0;i<matrix.size();i++)                    //Convert 2D array to 1D by row.\n        {\n            fill(row.begin(),row.end(),0);                  //Clear vector to start the row with i as starting row.\n            for(int j=i;j<matrix.size();j++)\n            {\n                for(int x=0;x<matrix[0].size();x++)         //Add next row\n                    row[x]+=matrix[j][x];\n                get_result(row);\n            }\n        }\n        return result;\n    }\n};\n```
[]