题目描述
给你一个数组 nums ，数组中只包含非负整数。定义 rev(x) 的值为将整数 x 各个数字位反转得到的结果。比方说 rev(123) = 321 ， rev(120) = 21 。我们称满足下面条件的下标对 (i, j) 是 好的 ：
0 <= i < j < nums.lengthnums[i] + rev(nums[j]) == nums[j] + rev(nums[i])
请你返回好下标对的数目。由于结果可能会很大，请将结果对 109 + 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 <= 1050 <= nums[i] <= 109
解法
方法一：式子变换 + 哈希表
对于下标对 $(i, j)$，如果满足条件，那么有 $nums[i] + rev(nums[j]) = nums[j] + rev(nums[i])$，即 $nums[i] - nums[j] = rev(nums[j]) - rev(nums[i])$。
因此，我们可以将 $nums[i] - rev(nums[i])$ 作为哈希表的键，统计每个键出现的次数。最后计算每个键对应的值的组合数，相加得到最终的答案。
注意答案的取模操作。
时间复杂度 $O(n \times \log M)$，其中 $n$ 和 $M$ 分别是数组 nums 的长度和数组 nums 中的最大值。空间复杂度 $O(n)$。
1
2
3
4
5
6
7
8
9
10
11
12 | class Solution:
def countNicePairs(self, nums: List[int]) -> int:
def rev(x):
y = 0
while x:
y = y * 10 + x % 10
x //= 10
return y
cnt = Counter(x - rev(x) for x in nums)
mod = 10**9 + 7
return sum(v * (v - 1) // 2 for v in cnt.values()) % mod
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 | class Solution {
public int countNicePairs(int[] nums) {
Map<Integer, Integer> cnt = new HashMap<>();
for (int x : nums) {
int y = x - rev(x);
cnt.merge(y, 1, Integer::sum);
}
final int mod = (int) 1e9 + 7;
long ans = 0;
for (int v : cnt.values()) {
ans = (ans + (long) v * (v - 1) / 2) % mod;
}
return (int) ans;
}
private int rev(int x) {
int y = 0;
for (; x > 0; x /= 10) {
y = y * 10 + x % 10;
}
return y;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 | class Solution {
public:
int countNicePairs(vector<int>& nums) {
auto rev = [](int x) {
int y = 0;
for (; x > 0; x /= 10) {
y = y * 10 + x % 10;
}
return y;
};
unordered_map<int, int> cnt;
for (int& x : nums) {
int y = x - rev(x);
cnt[y]++;
}
long long ans = 0;
const int mod = 1e9 + 7;
for (auto& [_, v] : cnt) {
ans = (ans + 1ll * v * (v - 1) / 2) % mod;
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | func countNicePairs(nums []int) (ans int) {
rev := func(x int) (y int) {
for ; x > 0; x /= 10 {
y = y*10 + x%10
}
return
}
cnt := map[int]int{}
for _, x := range nums {
y := x - rev(x)
cnt[y]++
}
const mod int = 1e9 + 7
for _, v := range cnt {
ans = (ans + v*(v-1)/2) % mod
}
return
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | function countNicePairs(nums: number[]): number {
const rev = (x: number): number => {
let y = 0;
while (x) {
y = y * 10 + (x % 10);
x = Math.floor(x / 10);
}
return y;
};
const mod = 10 ** 9 + 7;
const cnt = new Map<number, number>();
let ans = 0;
for (const x of nums) {
const y = x - rev(x);
ans = (ans + (cnt.get(y) ?? 0)) % mod;
cnt.set(y, (cnt.get(y) ?? 0) + 1);
}
return ans;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 | /**
* @param {number[]} nums
* @return {number}
*/
var countNicePairs = function (nums) {
const rev = x => {
let y = 0;
for (; x > 0; x = Math.floor(x / 10)) {
y = y * 10 + (x % 10);
}
return y;
};
const cnt = new Map();
for (const x of nums) {
const y = x - rev(x);
cnt.set(y, (cnt.get(y) | 0) + 1);
}
let ans = 0;
const mod = 1e9 + 7;
for (const [_, v] of cnt) {
ans = (ans + Math.floor((v * (v - 1)) / 2)) % mod;
}
return ans;
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 | public class Solution {
public int CountNicePairs(int[] nums) {
Dictionary<int, int> cnt = new Dictionary<int, int>();
foreach (int x in nums) {
int y = x - Rev(x);
cnt[y] = cnt.GetValueOrDefault(y, 0) + 1;
}
int mod = (int)1e9 + 7;
long ans = 0;
foreach (int v in cnt.Values) {
ans = (ans + (long)v * (v - 1) / 2) % mod;
}
return (int)ans;
}
private int Rev(int x) {
int y = 0;
while (x > 0) {
y = y * 10 + x % 10;
x /= 10;
}
return y;
}
}
|
方法二