AlgoPressAppearance
1814-统计一个数组中好对子的数目
题目描述
给你一个数组 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])
请你返回好下标对的数目。由于结果可能会很大，请将结果对 10^9 + 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^50 <= nums[i] <= 10^9
思路：暴力计算
直接按照题意，两重循环计算等式，可以算出结果，但是会超时。
尝试将第二个数组缓存起来，仍然会超时，因为时间复杂度为 O(n^2), n<=10^5
csharp
public class Solution {
private int rev(int num){
int result = 0;
while(num > 0){
result = result * 10 + (num % 10);
num = num / 10;
}
return result;
}
public int CountNicePairs(int[] nums) {
int count = 0;
int[] nums2 = new int[nums.Length];
for(int i=0; i<nums.Length; i++){
nums2[i] = rev(nums[i]);
}
for(int i=0; i<nums.Length -1; i++){
for(int j=i+1; j<nums.Length; j++){
if(nums[i] + nums2[j] == nums[j] + nums2[i]){
count++;
count = count % 1000000007;
}
}
}
return count;
}
}
思路：优化等式
把等式转化为 nums[i] - rev(nums[i]) == nums[j] - rev(nums[j]) 。
这一步非常重要，因为计算式只有一个index，这样我们只要一趟遍历就可以，遍历的过程中将结果使用哈希表缓存起来，可以加速取得结果。
csharp
public class Solution {
private int rev(int num){
int result = 0;
while(num > 0){
result = result * 10 + (num % 10);
num = num / 10;
}
return result;
}
public int CountNicePairs(int[] nums) {
//把等式转化为 nums[i] - rev(nums[i]) == nums[j] - rev(nums[j])
int count = 0;
Dictionary<int,int> dict = new Dictionary<int,int>();
int[] nums2 = new int[nums.Length];
for(int i=0; i<nums.Length; i++){
nums2[i] = nums[i] - rev(nums[i]);
//缓存到哈希表中去
if(dict.ContainsKey(nums2[i])){
count+=dict[nums2[i]];
dict[nums2[i]]++;
count = count % 1000000007;
}
else{
dict.Add(nums2[i],1);
}
}
return count;
}
}