【哈希表】【字符串】个人练习-Leetcode-1814. Count Nice Pairs in an Array

题目链接：https://leetcode.cn/problems/count-nice-pairs-in-an-array/description/

题目大意：给出一个数列nums[]，求nice对 ( i , j ) (i, j) (i,j)对数。nice对满足0 <= i < j < nums.length和nums[i] + rev(nums[j]) == nums[j] + rev(nums[i])，其中rev()是反转操作。

思路：一开始的思路是伪加法，取一个对，从低位开始加nums[i] + rev(nums[j]) 和nums[j] + rev(nums[i])，如果当前位不想等就返回false。能过样例，但nums[]太大时还是会超时。

class Solution {
public:
    bool iseq(string a, string b, string ra, string rb) {
        int p1 = a.size()-1, p2 = rb.size()-1, p3 = b.size()-1, p4 = ra.size()-1;
        int c1 = 0, c2 = 0;
        while (p1 >= 0 || p2 >= 0 || p3 >= 0 || p4 >= 0) {
            int v1 = c1;
            if (p1 >= 0) {
                v1 += (a[p1]-'0');
                p1--;
            }
            if (p2 >= 0) {
                v1 += (rb[p2] - '0');
                p2--;
            }                
            c1 = v1 / 10;
            v1 %= 10;

            int v2 = c2;
            if (p3 >= 0) {
                v2 += (b[p3]-'0');
                p3--;
            }
            if (p4 >= 0) {
                v2 += (ra[p4] - '0');
                p4--;
            }     
            c2 = v2 / 10;
            v2 %= 10;
            
            if (v1 != v2)
                return false;
        }
        if (c1 != c2)
            return false;
        return true;
    }

    int countNicePairs(vector<int>& nums) {
        vector<string> arr;
        vector<string> rev;
        for (auto x : nums) {
            string tmp = to_string(x);
            arr.emplace_back(tmp);
            while (tmp.back() == '0')
                tmp.pop_back();
            if (tmp.length() == 0)
                tmp = "0";
            reverse(tmp.begin(), tmp.end());
            rev.emplace_back(tmp);
        }

        int ans = 0;
        const int MX = 1e9+7;
        for (int i = 0; i < nums.size()-1; i++) {
            for (int j = i+1; j < nums.size(); j++) {
                if (iseq(arr[i], arr[j], rev[i], rev[j]))
                    ans = (ans+1) % MX;
            }
        }
        return ans;
    }
};

看了题解才发现可以转换原等式为nums[i] - rev(nums[i])) == nums[j] - rev(nums[j])，设 f ( x ) = n u m s [ x ] − r e v ( n u m s [ x ] ) f(x)=nums[x]-rev(nums[x]) f(x)=nums[x]−rev(nums[x])，用一个哈希表记录 f ( x ) f(x) f(x)的值，这样复杂度就降为 O ( N ) O(N) O(N)了。

完整代码

class Solution {
public:
    int countNicePairs(vector<int>& nums) {
        int ans = 0;
        const int MOD = 1e9+7;
        unordered_map<int, int> tb;
        for (auto num : nums) {
            string tmp = to_string(num);
            reverse(tmp.begin(), tmp.end());
            ans = (ans + tb[num - stoi(tmp)]) % MOD;
            tb[num - stoi(tmp)]++;
        }
        return ans;
    }
};