Medium

题目描述

给你一个由非负整数组成的数组 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])

返回好数对的数目。由于这个数目可能会很大，请返回对 10^9 + 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

解题思路

这道题的核心在于理解好数对的条件并进行数学变换。

题目要求找到满足 nums[i] + rev(nums[j]) == nums[j] + rev(nums[i]) 的下标对 (i, j)。

通过数学变换，我们可以将条件重新整理为：

  • nums[i] + rev(nums[j]) == nums[j] + rev(nums[i])
  • nums[i] - rev(nums[i]) == nums[j] - rev(nums[j])

这意味着两个元素能组成好数对，当且仅当它们与各自反转数的差值相等。

解题思路：

  1. 对于数组中的每个数字 nums[i]，计算 nums[i] - rev(nums[i]) 的值
  2. 使用哈希表统计每个差值出现的频次
  3. 对于每个差值，如果有 k 个数字具有相同的差值，那么它们可以组成 k * (k-1) / 2 个好数对
  4. 将所有组合数相加即为答案

优化处理： 为了避免最后一次性计算组合数可能导致的溢出，我们可以在遍历过程中累加结果：当遇到一个新的数字时，如果它的差值之前出现过 count 次，那么当前数字可以与之前的 count 个数字分别组成好数对。

时间复杂度为 O(n log m)，其中 n 是数组长度，m 是数字的最大值（反转数字需要 O(log m) 时间）。空间复杂度为 O(n)。

代码实现

class Solution {
public:
    int countNicePairs(vector<int>& nums) {
        const int MOD = 1e9 + 7;
        unordered_map<int, int> diffCount;
        long long result = 0;
        
        for (int num : nums) {
            int diff = num - reverse(num);
            result = (result + diffCount[diff]) % MOD;
            diffCount[diff]++;
        }
        
        return result;
    }
    
private:
    int reverse(int x) {
        int rev = 0;
        while (x > 0) {
            rev = rev * 10 + x % 10;
            x /= 10;
        }
        return rev;
    }
};

class Solution:
    def countNicePairs(self, nums: List[int]) -> int:
        MOD = 10**9 + 7
        diff_count = {}
        result = 0
        
        def reverse_num(x):
            return int(str(x)[::-1])
        
        for num in nums:
            diff = num - reverse_num(num)
            result = (result + diff_count.get(diff, 0)) % MOD
            diff_count[diff] = diff_count.get(diff, 0) + 1
            
        return result

public class Solution {
    public int CountNicePairs(int[] nums) {
        const int MOD = 1000000007;
        var diffCount = new Dictionary<int, int>();
        long result = 0;
        
        foreach (int num in nums) {
            int diff = num - ReverseNumber(num);
            if (diffCount.ContainsKey(diff)) {
                result = (result + diffCount[diff]) % MOD;
                diffCount[diff]++;
            } else {
                diffCount[diff] = 1;
            }
        }
        
        return (int)result;
    }
    
    private int ReverseNumber(int x) {
        int rev = 0;
        while (x > 0) {
            rev = rev * 10 + x % 10;
            x /= 10;
        }
        return rev;
    }
}

var countNicePairs = function(nums) {
    const MOD = 1e9 + 7;
    const diffCount = new Map();
    let result = 0;
    
    function reverseNumber(x) {
        return parseInt(x.toString().split('').reverse().join(''));
    }
    
    for (const num of nums) {
        const diff = num - reverseNumber(num);
        result = (result + (diffCount.get(diff) || 0)) % MOD;
        diffCount.set(diff, (diffCount.get(diff) || 0) + 1);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log m)n 是数组长度，m 是数字的最大值，反转数字需要 O(log m) 时间
空间复杂度O(n)哈希表最多存储 n 个不同的差值

相关题目