LeetCode-1814. 统计一个数组中好对子的数目【哈希表】

• 题目描述：
• 解题思路一：由题中nums[i]+rev(nums[j])=nums[j]+rev(nums[i])得到nums[i]-rev(nums[i])=nums[j]-rev(nums[j])
• 解题思路二：0
• 解题思路三：0

题目描述：

给你一个数组 nums ，数组中只包含非负整数。定义 rev(x) 的值为将整数 x 各个数字位反转得到的结果。比方说 rev(123) = 321 ， rev(120) = 21 。我们称满足下面条件的下标对 (i, j) 是 好的 ：

0 <= i < j < nums.length
nums[i] + rev(nums[j]) == nums[j] + rev(nums[i])
请你返回好下标对的数目。由于结果可能会很大，请将结果对 109 + 7 取余 后返回。

示例 1：

输入：nums = [42,11,1,97]
输出：2
解释：两个坐标对为：

• (0,3)：42 + rev(97) = 42 + 79 = 121, 97 + rev(42) = 97 + 24 = 121 。
• (1,2)：11 + rev(1) = 11 + 1 = 12, 1 + rev(11) = 1 + 11 = 12 。

示例 2：

输入：nums = [13,10,35,24,76]
输出：4

提示：

1 <= nums.length <= 10^5
0 <= nums[i] <= 10^9
https://leetcode.cn/problems/count-nice-pairs-in-an-array/description/

解题思路一：由题中nums[i]+rev(nums[j])=nums[j]+rev(nums[i])得到nums[i]-rev(nums[i])=nums[j]-rev(nums[j])

那么设f(i)=nums[i]−rev(nums[i])
现在要考虑的就是每次遍历到一个数i的时候，之前的f(x)与f(i)相同的个数，即是好的下标对的个数。用哈希表记录。

class Solution {
public:int countNicePairs(vector& nums) {const int MOD=1000000007;int res=0;//最终的结果unordered_map h;//记录对应f(i)的个数for(int i:nums){int temp=i,j=0;//temp存储num(i)的中间结果，j是rev(num(i))while(temp>0){j=j*10+temp%10;temp/=10;}//此时h[i-j]的数目即是好的下标对的个数。res=(res+h[i-j])%MOD;//i-j就是num(i)-rev(num(i))也就是f(i)h[i-j]++;}return res;}
};

时间复杂度：O(nlogC)//其中 n 为数组nums 的长度，C 为数组 nums中的数字范围。其中 O(log⁡C)为反转数位的时间复杂度。
空间复杂度：O(n)//哈希表

解题思路二：0

解题思路三：0