3128 直角三角形

题目描述#

给你一个二维 boolean 矩阵 grid 。

如果 grid 的 3 个元素的集合中，一个元素与另一个元素在同一行，并且与第三个元素在同一列，则该集合是一个直角三角形。3 个元素不必彼此相邻。

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

思路#

找到每行的1的个数，每列的1的个数，然后对于每个grid[i][j] == 1的点，计算以该点为直角顶点的直角三角形个数，即(rowCount[i] - 1) * (colCount[j] - 1)，累加到结果中。

乘法原理

代码#

func numberOfRightTriangles(grid [][]int) int64 {
	m := len(grid)
	n := len(grid[0])
	arrM := make([]int, n)
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			arrM[i] += grid[j][i]
		}
	}
	var ans int64

	for _, row := range grid {
		rowSum := -1
		for _, x := range row {
			rowSum += x
		}
		for j, x := range row {
			if x == 1 {
				ans += int64(arrM[j]-1) * int64(rowSum)
			}
		}
	}
	return ans

}