2001 可互换矩形的组数

题目描述#

给定一个 n 行的二维数组 rectangles，其中每一行表示一个矩形： rectangles[i] = [width_i, height_i]。

如果存在一对矩形 i、j（i < j）满足： width_i / height_i == width_j / height_j（实数除法），则称这两个矩形是 可互换的。

请计算数组中共有多少对可互换的矩形。

思路#

本题目是枚举右，维护左

对于 双变量问题，例如两数之和 a_i + a_j = t，可以枚举右侧的 a_j，把它转成 单变量问题：在 a_j 左侧查找是否存在 a_i = t - a_j。这可以用哈希表维护（遍历时用 map/set 记录已出现的数）。

代码#

class Solution {
    public long interchangeableRectangles(int[][] rectangles) {
        Map<Double, Integer> cnt = new HashMap<>();
        long ans = 0L;
        for (int[] rectangle : rectangles) {
            int width = rectangle[0];
            int height = rectangle[1];
            double k = width * 1.0 / height;
            if (cnt.containsKey(k)) {
                ans += cnt.get(k);
            }
            cnt.merge(k, 1, Integer::sum);
        }
        return ans;
    }
}