直角三角形

leetcode

题目：

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

• 如果 grid 中 3 个元素满足：一个元素与另一个元素在 同一行，同时与第三个元素在 同一列 ，那么这 3 个元素称为一个 直角三角形 。这 3 个元素互相之间不需要相邻。
• 1 <= grid.length <= 1000
• 1 <= grid[i].length <= 1000
• 0 <= grid[i][j] <= 1

看完题目，就有了思路，统计每行每列1的个数，然后遍历整个 grid数组，当当前点 grid[i][j]为1时，以当前点为直第i行1的个数减去1角三角形的两个边的交汇点，那么以这个点可以组成的三角形个数为第j列1的个数减去1然后乘上第i行1的个数减去1。然后求和即可

for (int i = 0; i < m; i++) 
{
    for (int j = 0; j < n; j++) 
    {
        if (grid[i][j] == 1) 
        {
            row[i]++;
            column[j]++;
        }
    }
}
long long  ans = 0;
for (int i = 0; i < m; i++)
{
    for (int j = 0; j < n; j++)
    {
        if (grid[i][j] == 1)
        {
            ans += (row[i] - 1) * (column[j] - 1);
        }
    }
}

总结

今天这道题很简单，只需要相同如何判断三角形是否存在即可。