力扣3128. 直角三角形

力扣3128. 直角三角形

题目解析及思路

题目要求找到矩阵中的直角三角形，不必相邻

套路：三个点**枚举(中间)**直角顶点更容易计算

对于(i,j)的直角顶点，构成直角三角形有多少个？

设第 i 行有 rowSum 个 1，第 j 列有 colSum 个 1。根据乘法原理，直角顶点为 (i,j) 的「直角三角形」有

(rowSum−1)⋅(colSum−1)个

那么也就是说我们要求出rowSum和colSum，再通过乘法原理计算答案即可

实现见代码

代码

class Solution {
public:long long numberOfRightTriangles(vector<vector<int>>& grid) {//n为列数int n = grid[0].size();//提前-1vector<int> col_sum(n,-1);for(auto &row : grid)//遍历每一列 再对应列+=row[j]for(int j=0;j<n;j++)col_sum[j] += row[j];long long ans = 0;for(auto &row : grid){//reduce求和，同样提前-1int row_sum = reduce(row.begin(), row.end()) - 1;for(int j=0;j<n;j++)//枚举当前点作为直角顶点if(row[j] == 1)ans += row_sum * col_sum[j];}return ans;}
};