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

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

难度中等4

给你一个数组 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])

请你返回好下标对的数目。由于结果可能会很大，请将结果对 1e9 + 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

数学变形

解题思路
根据条件：$a+rev(b)=b+rev(a)$可以推导出:

$$
\begin{cases} a=b+rev(a)-rev(b)\ b=a+rev(b)-rev(a) \end{cases}
$$
再变换可以得到$:a-rev(a)=b-rev(b)$
所以统计好对子的数目就是统计:$nums[i]-rev(nums[i])$值相等的对子数目。
可以用字典map来统计每个数的$nums[i]-rev(nums[i])$值出现的个数，最后再用累加公式计算字典中每个value，得到对应的key的好对子数目，把每个key的好对子数目相加就是数组中好对子的数目。

注意
对子要成对出现，只有一个时不能组成对子

还需要用到组合公式:
$$
c^{2}_n
$$

作者：Ray_Super_Wang
链接：https://leetcode-cn.com/problems/count-nice-pairs-in-an-array/solution/arevbbrevaa-revab-revb-by-ray_super_wang-fh5q/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution {
    public int countNicePairs(int[] nums) {
        int mod = (int)1e9+7;
        int n=nums.length;

        Map<Integer,Integer> map=new HashMap<>();
        for(int i=0;i<n;i++){
            int val=nums[i] - rev(nums[i]);
            int count=map.getOrDefault(val,0);
            count++;
            map.put(val,count);
        }

        long res=0;
        for(Map.Entry<Integer,Integer> entry:map.entrySet()){
            int key=entry.getKey();
            int val=entry.getValue();
            // 注意这里要转型
            res = (res + (long)val*(val-1)/2) % mod;
        }

        return(int)(res % mod);

    }
    public int rev(int num){
        int res=0;
        while(num > 0){
            res *= 10;
            res += (num % 10);
            num /= 10;
        }
        return res;
    }
}

赏

谢谢你请我吃糖果

微信