原题链接在这里：

题目：

Given a grid where each entry is only 0 or 1, find the number of corner rectangles.

A corner rectangle is 4 distinct 1s on the grid that form an axis-aligned rectangle. Note that only the corners need to have the value 1. Also, all four 1s used must be distinct.

 

Example 1:

Input: grid = [[1, 0, 0, 1, 0], [0, 0, 1, 0, 1], [0, 0, 0, 1, 0], [1, 0, 1, 0, 1]]Output: 1Explanation: There is only one corner rectangle, with corners grid[1][2], grid[1][4], grid[3][2], grid[3][4].

Example 2:

Input: grid = [[1, 1, 1], [1, 1, 1], [1, 1, 1]]Output: 9Explanation: There are four 2x2 rectangles, four 2x3 and 3x2 rectangles, and one 3x3 rectangle.

Example 3:

Input: grid = [[1, 1, 1, 1]]Output: 0Explanation: Rectangles must have four distinct corners.

Note:

1. The number of rows and columns of grid will each be in the range [1, 200].
2. Each grid[i][j] will be either 0 or 1.
3. The number of 1s in the grid will be at most 6000.

题解：

When there is a new row, within this row, row[c1] and row[c2] are both 1.

Then number of newly constructed rectanges are number of previous rows having both exact same two columns mark as 1.

To maintain number of two 1 on c1 and c2, use a hash function c1*200+c2. 

Time Complexity: O(r*c^2). r = grid.length. c = grid[0].length.

Space: O(c^2).

AC Java: 

1 class Solution { 2     public int countCornerRectangles(int[][] grid) { 3         int res = 0; 4         HashMap
     
       hm = new HashMap<>(); 5         for(int [] row : grid){ 6             for(int c1 = 0; c1