统计一个数组中好对子的数目

难度: 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⁹ + 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⁵
0 <= nums[i] <= 10⁹

Submission

运行时间: 142 ms

内存: 26.6 MB

from collections import Counter


class Solution:
    def countNicePairs(self, nums: List[int]) -> int:
        # m=10**9+7
        # # 直接暴力 不是很行
        # r=[]
        # n=len(nums)
        # cnt=0
        
        # for i in nums:
        #     s=0
        #     while i>0:
        #         s*=10
        #         s+=i%10
        #         i//=10
        #     r.append(s)
        
        # # for i in range(n):
        # #     for j in range(i+1,n):
        # #         if nums[i]+r[j]==nums[j]+r[i]:
        # #             cnt +=1
        # # return cnt%m

        # """
        # 需要对公式进行变形 
        # 左为i 右为j
        # 看出i 与 ri的差相等
        # 相等的即可进行组合 ，求组合数
        # """
        # c=Counter()
        # for i in range(n):
        #     c[nums[i]-r[i]]+=1
        # return sum([i*(i-1)//2 for i in c.values()])%m

        # 简化代码

        return sum([i*(i-1)//2 for i in Counter([j-int(str(j)[::-1]) for j in nums]).values()])%(10**9+7)

Explain

题解的核心思路是通过数学变换将原问题简化。具体地，利用题目给出的条件 nums[i] + rev(nums[j]) == nums[j] + rev(nums[i])，可以推导出 nums[i] - rev(nums[i]) == nums[j] - rev(nums[j])。这意味着，只要两个数 nums[i] 和 nums[j] 的差值与其反转值的差相同，这两个数就构成一个好对。基于此，我们可以使用哈希表（通过Counter类实现）来统计每个差值出现的次数。最后，对于哈希表中的每个元素，计算其组合数 C(n, 2) = n*(n-1)/2，即这个差值对应的好对数。最终结果为所有组合数的总和。

时间复杂度: O(n)

空间复杂度: O(n)

from collections import Counter


class Solution:
    def countNicePairs(self, nums: List[int]) -> int:
        # 定义模数
        mod = 10**9+7
        # 计算所有数字的反转差值
        diff = [num - int(str(num)[::-1]) for num in nums]
        # 用哈希表统计差值出现的频率
        count = Counter(diff)
        # 计算所有的好对子数目，每个差值对应的组合数
        result = sum((count[x] * (count[x] - 1) // 2 for x in count)) % mod
        return result

Explore

在Python中，将数字转换为字符串并反转后，再转换回整数时，字符串前导的0会自然消失。例如，数字1200反转字符串形式为'0021'，再转换为整数时变成21。因此，`int(str(num)[::-1])`能够正确处理以0结尾的数字，而不需要任何特殊的处理。这种转换方式在所有可能的整数输入上都是有效的，因为Python的整数转换会忽略字符串前导的0。

在这个解法中，哈希表`count`的键代表的是数组中每个元素`num`与其数字反转`rev(num)`之差的值。根据题目的条件，当两个数的差值与其反转值的差相同，即`nums[i] - rev(nums[i]) == nums[j] - rev(nums[j])`时，这两个数构成一个好对。因此，通过统计每个差值出现的频率，我们可以快速找到所有可能的好对子。使用这个差值作为键的好处是能够将问题从O(n^2)的复杂度降低到O(n)，因为我们只需遍历一次数组，并利用哈希表（计数器）来统计差值出现的次数。

组合数公式`C(n, 2) = n*(n-1)/2`在计算时可能会导致整数溢出，尤其是在`n`的值非常大时。在Python中，虽然整数类型可以自动处理较大的数，但在某些语言中，如C++或Java，可能需要特别注意整数溢出的问题。为了避免这种情况，在进行乘法运算前，应该先进行取模操作或使用长整形数据类型。在当前的Python实现中，通过在每次计算组合数后立即对结果取模`mod = 10**9+7`，可以有效避免溢出问题，并保证结果的正确性。

在当前的解法中，如果`nums`数组为空或只有一个元素，函数仍能正确处理这些边界情况。当数组为空时，`diff`列表也将为空，`count`计数器将不包含任何元素，因此最终结果为0。同样地，如果数组只含有一个元素，那么不可能形成任何好对子，因为好对子需要至少两个元素。在这种情况下，`count`计数器中每个键对应的值也不足以形成任何组合（需要至少两个），故最终结果同样为0。这些边界情况已经被算法逻辑自然而然地处理了。