Using the same example as the question's：
separate it into four parts based on the given rectangle:
a = (3,5) b = (0,1,4, 6,3,2) c = (1,4,1) d = (2,0,1, 1,0,1, 0,3,0)
"d" is what we need to calculate here, so let's make it forward:
A = a = sumRegion(0,0, row1 - 1, col1 - 1) B = a + b = sumRegion(0,0, row1 - 1, col2) C = a + c = sumRegion(0,0, row2, col1 - 1) D = a + b + c + d = sumRegion(0,0, row2, col2)
so it's easy to get this: d = (A+D) - (B+C)
The rest is that how to calculate A, B, C and D.
Yes, just for-loop one time the matrix, we can get them.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.