LeeCode《可以读通讯稿的组数》ac题解

题目描述
可以读通讯稿的组数

解题思路和技巧
首先数据范围 >= 1E5,双重循环暴力肯定不可以
当发现顺着题目的思路进行模拟会超时时，必须要换个思路进行思考
例如这道题目，如果要两两数进行组队，再判断，肯定会超时的
所以就不要一直想着怎样使两两数组队了
向题目中有出现公式的这种题目，可以尝试着移项寻找一下规律
例如这道题目
【17，28】可以组队
17 + 82 = 71 + 28
82 - 28 = 71 - 17
你就会发现 镜像数字 - 数字本身 的结果相等的数字是可以进行组队的
那么只需要将这些数字集中在一起
计算结果时，只需要从每一队数字中取出两个数字即可，排列组合的知识，就是计算C(n, 2)

代码实现

class Solution {
public:
    unordered_map  m;
    int numberOfPairs(vector& nums) {
        long long res = 0;
        for (auto x : nums)
        {
            string a = to_string(x);
            reverse(a.begin(), a.end());
            int na = atoi(a.c_str());
            m[na - x] ++;
        }
        for (auto x : m)
        {
            res += x.second * (x.second - 1) / 2;
        }
        return res % (1000000000+7);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19