LeetCode-1128. 等价多米诺骨牌对的数量

给你一个由一些多米诺骨牌组成的列表 dominoes。

如果其中某一张多米诺骨牌可以通过旋转 0 度或 180 度得到另一张多米诺骨牌，我们就认为这两张牌是等价的。

形式上，dominoes[i] = [a, b] 和 dominoes[j] = [c, d] 等价的前提是 a==c 且 b==d，或是 a==d 且 b==c。

在 0 <= i < j < dominoes.length 的前提下，找出满足 dominoes[i] 和 dominoes[j] 等价的骨牌对 (i, j) 的数量。

 

示例：

输入：dominoes = [[1,2],[2,1],[3,4],[5,6]]
输出：1
 

提示：

1 <= dominoes.length <= 40000
1 <= dominoes[i][j] <= 9

分析：常规O(n2)复杂度超时，不考虑

满足等价的另一种表达为 a+b = c+d 且 |a-b| = |c-d|

将结果拼装作为key，每次相同则value+1 ，这样只需遍历一次即可

注：结果应该为1+2+3+···+value，因为重复数组也算次数

public int numEquivDominoPairs(int[][] dominoes) {
    int count = 0;
    Map<String,Integer> map = new HashMap();
    for (int i = 0; i < dominoes.length; i++) {
        int[] temp = dominoes[i];
        int sum = temp[0] + temp[1];
        int abs = Math.abs(temp[0] - temp[1]);
        String key = sum +"@" + abs;
        if (map.get(key) == null) {
            map.put(key,0);
        } else {
            int value = map.get(key);
            map.put(key,value+1);
        }
    }
    for (Integer value:map.values()) {
        if (value > 0 ) {
            count = count +getSum(value);
        }
    }
    return count;
}

private int getSum(int n) {
    int sum = 0;
    for (int i = 1; i <= n ; i++) {
        sum = sum + i;
    }
    return sum;
}