统计一个数组中好对子的数目
难度:
标签:
题目描述
代码结果
运行时间: 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结尾的数字?
▷🦆
哈希表`count`中的键表示什么意义,并且它如何帮助我们找到符合条件的好对子?
▷🦆
你提到的组合数公式`C(n, 2) = n*(n-1)/2`在哪些情况下可能导致计算上的错误,比如整数溢出等?
▷🦆
在你的解法中,有没有考虑到当`nums`数组为空或只有一个元素时的边界情形?
▷