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

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

题目大意：给出一个数列nums[]，求nice对$(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)=nums[x]-rev(nums[x])$，用一个哈希表记录$f(x)$的值，这样复杂度就降为$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;}
};