leetcode
leetcode 1601 ~ 1650
统计一个数组中好对子的数目

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

难度:

标签:

题目描述

代码结果

运行时间: 142 ms, 内存: 26.6 MB


/*
题目思路:
1. 使用 Java Streams 简化对数组的遍历和处理。
2. 计算每个数的反转值并存储在一个 HashMap 中。
3. 通过组合所有可能的下标对 (i, j),过滤出满足条件的对数。
4. 计数满足条件的对数并对结果取余。
*/

import java.util.*;
import java.util.stream.IntStream;

public class GoodIndexPairsStream {
    private static final int MOD = 1000000007;

    public static int countGoodPairs(int[] nums) {
        Map<Integer, Integer> revMap = new HashMap<>();
        Arrays.stream(nums).forEach(num -> revMap.put(num, rev(num)));

        long count = IntStream.range(0, nums.length)
                .boxed()
                .flatMap(i -> IntStream.range(i + 1, nums.length)
                        .filter(j -> (nums[i] + revMap.get(nums[j])) % MOD == (nums[j] + revMap.get(nums[i])) % MOD)
                        .boxed())
                .count();

        return (int) (count % MOD);
    }

    private static int rev(int x) {
        int rev = 0;
        while (x > 0) {
            rev = rev * 10 + x % 10;
            x /= 10;
        }
        return rev;
    }

    public static void main(String[] args) {
        int[] nums1 = {42, 11, 1, 97};
        int[] nums2 = {13, 10, 35, 24, 76};
        System.out.println(countGoodPairs(nums1)); // 输出: 2
        System.out.println(countGoodPairs(nums2)); // 输出: 4
    }
}

解释

方法:

题解的核心思路是通过数学变换将原问题简化。具体地,利用题目给出的条件 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)

代码细节讲解

🦆
在函数`countNicePairs`中,你是如何确保`int(str(num)[::-1])`操作在所有输入情况下都能正确执行,例如对于以0结尾的数字?
在Python中,将数字转换为字符串并反转后,再转换回整数时,字符串前导的0会自然消失。例如,数字1200反转字符串形式为'0021',再转换为整数时变成21。因此,`int(str(num)[::-1])`能够正确处理以0结尾的数字,而不需要任何特殊的处理。这种转换方式在所有可能的整数输入上都是有效的,因为Python的整数转换会忽略字符串前导的0。
🦆
哈希表`count`中的键表示什么意义,并且它如何帮助我们找到符合条件的好对子?
在这个解法中,哈希表`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`在哪些情况下可能导致计算上的错误,比如整数溢出等?
组合数公式`C(n, 2) = n*(n-1)/2`在计算时可能会导致整数溢出,尤其是在`n`的值非常大时。在Python中,虽然整数类型可以自动处理较大的数,但在某些语言中,如C++或Java,可能需要特别注意整数溢出的问题。为了避免这种情况,在进行乘法运算前,应该先进行取模操作或使用长整形数据类型。在当前的Python实现中,通过在每次计算组合数后立即对结果取模`mod = 10**9+7`,可以有效避免溢出问题,并保证结果的正确性。
🦆
在你的解法中,有没有考虑到当`nums`数组为空或只有一个元素时的边界情形?
在当前的解法中,如果`nums`数组为空或只有一个元素,函数仍能正确处理这些边界情况。当数组为空时,`diff`列表也将为空,`count`计数器将不包含任何元素,因此最终结果为0。同样地,如果数组只含有一个元素,那么不可能形成任何好对子,因为好对子需要至少两个元素。在这种情况下,`count`计数器中每个键对应的值也不足以形成任何组合(需要至少两个),故最终结果同样为0。这些边界情况已经被算法逻辑自然而然地处理了。

相关问题