3128：直角三角形（1540 分）

力扣第 129 场双周赛第 2 题

题目

给你一个二维 boolean 矩阵 grid 。

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

注意：

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

示例 1：

示例 2：

示例 3：

提示：

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

分析

• 遍历每个 1 作为中间顶点统计即可
• 预处理每行/列的 1 的个数，节省时间

解答

1
2
3
4
5
6
7
8

class Solution:
    def numberOfRightTriangles(self, grid: List[List[int]]) -> int:
        C = [sum(col)-1 for col in zip(*grid)]
        res = 0
        for i,row in enumerate(grid):
            a = sum(row)-1
            res += a*sum(b for x,b in zip(row,C) if x) 
        return res

248 ms