统计一个数组中好对子的数目【LC1814】
You are given an array nums that consists of non-negative integers. Let us define rev(x) as the reverse of the non-negative integer x. For example, rev(123) = 321, and rev(120) = 21. A pair of indices (i, j) is nice if it satisfies all of the following conditions:
- 0 <= i < j < nums.length
- nums[i] + rev(nums[j]) == nums[j] + rev(nums[i])
Return the number of nice pairs of indices. Since that number can be too large, return it modulo 109 + 7.
- 思路：如果两个数满足好对子，那么这两个数反转后的变化量相同。因此可以使用哈希表存放反转后的变化量及其次数count，该变化量存在的所有好对子个数为count∗(count−1)/2
- 实现
class Solution { public int countNicePairs(int[] nums) { int MOD = (int)(1e9 + 7); Map<Integer,Long> valToCount = new HashMap<>(); for (int num : nums){ int change = num - rev(num); valToCount.put(change, valToCount.getOrDefault(change, 0L) + 1); } long res = 0; for (long count : valToCount.keySet()){ res = (res + count * (count - 1) / 2) % MOD; } return (int)res; } public int rev(int num){ int res = 0; while (num != 0){ res = res * 10 + num % 10; num /= 10; } return res; } }
。复杂度
- 时间复杂度：O(nlogm+n)，n为数组长度，对数组中每个数求取变化量放入哈希表的时间复杂度为O(nlogm)
- 空间复杂度：O(n)
- 优化：一次遍历，由于哈希表里保存的是以前某个变化量出现的次数，因此可以直接累加该变化量以前的出现次数count，即为以当前数x为j，数组中共有count个i
- 实现
class Solution { public int countNicePairs(int[] nums) { int MOD = (int)(1e9 + 7); Map<Integer,Integer> valToCount = new HashMap<>(); int res = 0; for (int num : nums){ int change = num - rev(num); res = (res + valToCount.getOrDefault(change, 0)) % MOD; valToCount.put(change, valToCount.getOrDefault(change, 0) + 1); } return res; } public int rev(int num){ int res = 0; while (num != 0){ res = res * 10 + num % 10; num /= 10; } return res; } }
。复杂度
- 时间复杂度：O(nlogm)，n为数组长度，m 为数组中的最大值
- 空间复杂度：O ( n )
。耗费时间多于先存储后计算，猜测原因未反复累加取余耗费的时间较高。
。空间优于先存储后计算，因为没有使用long类型变量
