日期: 2024 年 8 月 2 日

目标

给你一个二维 boolean 矩阵 grid 。

请你返回使用 grid 中的 3 个元素可以构建的 直角三角形 数目，且满足 3 个元素值 都 为 1 。

注意：

• 如果 grid 中 3 个元素满足：一个元素与另一个元素在 同一行，同时与第三个元素在 同一列 ，那么这 3 个元素称为一个 直角三角形 。这 3 个元素互相之间不需要相邻。

示例 1：

0 1 0
0 1 1
0 1 0

输入：grid = [[0,1,0],[0,1,1],[0,1,0]]
输出：2
解释：有 2 个直角三角形。

示例 2：

1 0 0 0
0 1 0 1
1 0 0 0

输入：grid = [[1,0,0,0],[0,1,0,1],[1,0,0,0]]
输出：0
解释：没有直角三角形。

示例 3：

1 0 1
1 0 0
1 0 0

输入：grid = [[1,0,1],[1,0,0],[1,0,0]]
输出：2
解释：有两个直角三角形。

说明：

• 1 <= grid.length <= 1000
• 1 <= grid[i].length <= 1000
• 0 <= grid[i][j] <= 1

思路

有一个二进制矩阵，如果元素本身为1，且同行和同列存在其它元素也为1，则称这三个元素组成了直角三角形。求矩阵中直角三角形的数目。

常规的解法是从左到右从上到下遍历矩阵元素，如果当前元素为1，则将其视为可能的直角顶点，然后向左右、向上下查找，看是否有元素为1。如果纵向为1的元素个数为 m，横向为1的元素个数为 n，那么以当前元素为直角顶点的直角三角形有 m * n 个。矩阵元素个数最多 10^6 个，然后遍历上下、左右元素最多 2 * 10^3，这个解法肯定会超时。

我们希望遍历到某个节点时可以直接获取到上下、左右的可选元素个数。为此，我们可以将各行各列元素值为1的元素个数先求出来，然后判断当前节点是否为1，为1就拿相应行列的个数减1相乘。这样时间复杂度可降为为 O(mn)。

从leetcode结果来看，这里面有几个可以提高性能的操作：

1. 行、列求和写在同一个循环内可以大幅提高性能
2. 循环内部判断元素是否为1可以省去，因为是二进制数组，可以直接拿当前元素值相乘，可以大幅提高效率
3. 将行和数组改为局部变量可以稍微提高性能

代码

/**
 * @date 2024-08-02 14:37
 */
public class NumberOfRightTriangles3128 {

    public long numberOfRightTriangles(int[][] grid) {
        long res = 0;
        int m = grid.length;
        int n = grid[0].length;
        int[] colSum = new int[n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                colSum[j] += grid[i][j];
            }
        }
        for (int i = 0; i < m; i++) {
            int rowSum = 0;
            for (int j = 0; j < n; j++) {
                rowSum += grid[i][j];
            }
            for (int j = 0; j < n; j++) {
                res += grid[i][j] * (rowSum - 1) * (colSum[j] - 1);
            }
        }
        return res;
    }
}

性能