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

1 题目

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

给你一个数组nums，数组中只包含非负整数。定义rev(x)的值为将整数x各个数字位反转得到的结果。比方说rev(123) = 321，rev(120) = 21。我们称满足下面条件的下标对(i, j)是好的：

• 0 <= i < j < nums.length
• nums[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 <= 105
• 0 <= nums[i] <= 109

2 代码实现

class Solution { private: long long rev(long long x){ long long res = 0 ; for (; x > 0 ; x /= 10 ){ res = res * 10 + x % 10 ; } return res ; } public: int countNicePairs(vector<int>& nums) { const int mod = 1e9 + 7 ; int count = 0 ; unordered_map <long long , int > diffMap ; for (int i = 0 ; i < nums.size() ; i ++){ long long diff = (long long )nums[i] - rev((long long )nums[i] ); count = (count + diffMap[diff]) % mod ; diffMap[diff] ++; } return count ; } };

又这么乱写，写一半...

我大概的想法，就是nums[i] + rev(nums[j]) == nums[j] + rev(nums[i])变形成nums[i] - rev(nums[i]) ，i 和 j 取到相等 。怎么比对呢，unordered_map吗，不知道怎么写。

class Solution { private: int rev (int x ){ int res = 0 ; for ( ; x > 0 ; x /= 10){ res = res * 10 + x % 10 ; } return res ; } public: int countNicePairs(vector<int>& nums) { int count = 0 ; for (int i = 0 ; i < nums.size() ; i++){ } } };

补全代码

你现在的核心需求是把思路（将条件变形为nums[i] - rev(nums[i]) == nums[j] - rev(nums[j])，并用哈希表统计该值的出现次数来计算好对子数目）转化为完整的 C++ 代码，补全你写了一半的逻辑。

解题思路

1. 公式变形：原条件nums[i] + rev(nums[j]) == nums[j] + rev(nums[i])可变形为nums[i] - rev(nums[i]) == nums[j] - rev(nums[j])，我们把这个差值记为diff。
2. 哈希表统计：遍历数组时，用哈希表（unordered_map）记录每个diff出现的次数。对于当前元素的diff，它能和之前所有相同diff的元素组成好对子，因此直接将哈希表中该diff的现有次数加到结果中，再更新哈希表。
3. 取模处理：由于结果可能很大，每一步都要对10^9 + 7取余。

完整代码实现

#include <vector> #include <unordered_map> using namespace std; class Solution { private: // 反转数字x的各位（注意x是非负整数） long long rev(long long x) { // 用long long避免数值溢出 long long res = 0; for (; x > 0; x /= 10) { res = res * 10 + x % 10; } return res; } public: int countNicePairs(vector<int>& nums) { const int MOD = 1e9 + 7; int count = 0; unordered_map<long long, int> diffMap; // 存储diff值对应的出现次数 for (int num : nums) { // 计算当前数字的diff = num - rev(num) long long diff = (long long)num - rev(num); // 强转避免溢出 // 现有相同diff的数量就是能组成的新好对子数，加到结果中 count = (count + diffMap[diff]) % MOD; // 更新哈希表，当前diff的出现次数+1 diffMap[diff]++; } return count; } }; // 测试用例 // 示例1：输入[42,11,1,97]，输出2 // 示例2：输入[13,10,35,24,76]，输出4

代码关键部分解释

1. rev 函数的优化：将参数和返回值改为long long，因为nums[i]最大为10^9，反转后也可能接近10^9，用long long可以避免整数溢出（比如num=10^9时，int可能存不下反转后的数）。
2. diff 的计算：同样用long long存储diff，防止num - rev(num)的结果超出int范围。
3. 哈希表的使用：diffMap的键是diff值，值是该diff出现的次数。遍历数组时，先取diffMap[diff]（即之前出现过的相同diff的元素数量）加到结果中，再将diffMap[diff]加 1。这一步的逻辑是：当前元素能和之前所有相同 diff 的元素组成好对子，比如diff已经出现了k次，当前元素加入后会新增k个好对子。
4. 取模操作：每次更新count时都对MOD取余，确保结果不会溢出且符合题目要求。

测试用例验证

以示例 1nums = [42,11,1,97]为例：

• 42 的 diff：42 - 24 = 18 → diffMap 中 18 的次数为 0，count=0，diffMap [18]=1
• 11 的 diff：11 - 11 = 0 → diffMap 中 0 的次数为 0，count=0，diffMap [0]=1
• 1 的 diff：1 - 1 = 0 → diffMap 中 0 的次数为 1，count=1，diffMap [0]=2
• 97 的 diff：97 - 79 = 18 → diffMap 中 18 的次数为 1，count=2，diffMap [18]=2最终结果为 2，符合示例要求。

总结

1. 核心变形：将原条件转化为nums[i] - rev(nums[i]) == nums[j] - rev(nums[j])，把问题转化为统计相同差值的元素对数。
2. 哈希表效率：使用unordered_map统计差值出现次数，遍历数组的时间复杂度为O(n)，能处理n=10^5的规模（避免了双重循环的O(n^2)超时问题）。
3. 溢出处理：使用long long存储反转后的数和差值，防止整数溢出导致错误。

diffMap[diff]的含义

你现在的核心疑问是代码中diffMap[diff]的含义，以及它在统计好对子数目时的作用。我会先解释这个表达式的意思，再结合代码逻辑说明它的具体作用。

diffMap[diff]的含义

在 C++ 的unordered_map<long long, int> diffMap中：

• 键（key）：是long long类型的diff值（即nums[i] - rev(nums[i])）。
• 值（value）：是int类型的数字，表示这个diff值在当前遍历位置之前已经出现过的次数。
• diffMap[diff]就是获取键为diff对应的 value 值：
  1. 如果diff这个键已经存在于哈希表中，返回的是它对应的出现次数。
  2. 如果diff这个键不存在于哈希表中，C++ 会自动将这个键插入到哈希表中，并将其对应的 value 初始化为0，然后返回 0。

结合代码逻辑理解diffMap[diff]的作用

我们的核心逻辑是：两个元素的diff相等，就可以组成一个好对子。遍历数组时，diffMap[diff]的作用是统计 “当前元素能和之前多少个元素组成好对子”。

代码执行过程拆解（以示例 1nums = [42,11,1,97]为例）

1. 遍历第一个元素 42：
   • 计算diff = 42 - rev(42) = 42 - 24 = 18。
   • diffMap[18]：此时哈希表中没有 18 这个键，返回 0 →count = 0 + 0 = 0。
   • 执行diffMap[18]++→ 哈希表中 18 的次数变为 1。
2. 遍历第二个元素 11：
   • 计算diff = 11 - rev(11) = 11 - 11 = 0。
   • diffMap[0]：哈希表中没有 0 这个键，返回 0 →count = 0 + 0 = 0。
   • 执行diffMap[0]++→ 哈希表中 0 的次数变为 1。
3. 遍历第三个元素 1：
   • 计算diff = 1 - rev(1) = 1 - 1 = 0。
   • diffMap[0]：哈希表中已有 0 这个键，返回 1 →count = 0 + 1 = 1。
   • 执行diffMap[0]++→ 哈希表中 0 的次数变为 2。
4. 遍历第四个元素 97：
   • 计算diff = 97 - rev(97) = 97 - 79 = 18。
   • diffMap[18]：哈希表中已有 18 这个键，返回 1 →count = 1 + 1 = 2。
   • 执行diffMap[18]++→ 哈希表中 18 的次数变为 2。最终count为 2，和示例 1 的结果一致。

补充：代码中的一个隐藏问题

你的rev函数中，long long res ;没有初始化，这会导致未定义行为（res 的初始值是随机的垃圾值，反转数字的结果会出错）。需要将其初始化为 0：

(之前写错的...)

long long rev(long long x){ long long res = 0; // 必须初始化！ for (; x > 0 ; x /= 10 ){ res = res * 10 + x % 10 ; } return res ; }

总结

1. diffMap[diff]的核心含义：获取当前diff值在遍历到当前元素之前出现过的次数，这个次数就是当前元素能组成的新好对子数量。
2. 哈希表的工作流程：先通过diffMap[diff]累加对子数，再将diff的出现次数加 1，确保后续元素能统计到当前元素。
3. 关键修复点：rev函数中的res必须初始化为 0，否则会因垃圾值导致反转结果错误。

这个map里面的key 和 value 可以这么直接定义进去吗？

unordered_map <long long , int > diffMap ; for (int i = 0 ; i < nums.size() ; i ++){ long long diff = (long long )nums[i] - rev((long long )nums[i] ); count = (count + diffMap[diff]) % mod ; diffMap[diff] ++; }

你现在的核心疑问是：在代码中直接使用diffMap[diff]这种方式，能否自动将diff作为 key、对应的值作为 value 存入unordered_map中，以及这种用法的底层逻辑是什么。

直接结论

可以的。C++ 的unordered_map（包括map）支持通过[]运算符直接访问 / 插入键值对，这是它的一个核心特性，你的代码中这种用法是完全合法且符合常规写法的。

底层逻辑与具体行为

当你执行diffMap[diff]时，unordered_map会做以下两件事：

1. 检查diff这个 key 是否已经存在：
   • 如果存在：直接返回该 key 对应的 value 的引用（可以读取或修改这个值）。
   • 如果不存在：自动将这个 key 插入到哈希表中，并将其对应的 value 初始化为该类型的默认值（对于int类型，默认值是0），然后返回这个默认值的引用。

结合你的代码理解具体执行过程

你的代码中这两行是核心：

count = (count + diffMap[diff]) % mod ; // 步骤1：访问diffMap[diff] diffMap[diff] ++; // 步骤2：修改diffMap[diff]

我们以示例中diff=0（第一次出现）为例：

1. 步骤 1：diff=0不存在于diffMap中，unordered_map自动插入key=0，value=0，然后返回0，所以count加上的是0。
2. 步骤 2：对diffMap[0]的引用执行++操作，此时value从0变成1，哈希表中就存储了0:1的键值对。

当diff=0第二次出现时：

1. 步骤 1：diff=0已经存在，直接返回对应的value=1，count加上1。
2. 步骤 2：value从1变成2，哈希表中存储0:2。

补充：这种用法与find/insert的对比

如果你担心自动插入的行为（比如只想读取不想插入），可以用find方法先判断 key 是否存在，比如：

// 不自动插入的写法（仅读取） auto it = diffMap.find(diff); int current = 0; if (it != diffMap.end()) { current = it->second; // 存在则取对应的值 } count = (count + current) % mod; diffMap[diff]++; // 这里还是会插入（如果不存在）

但在你的代码场景中，我们本来就需要将diff插入到哈希表中并统计次数，所以直接用[]运算符是最简洁、最高效的写法，完全不需要额外的find判断。

验证示例

我们用一段简单的代码演示这个特性：

#include <iostream> #include <unordered_map> using namespace std; int main() { unordered_map<long long, int> diffMap; // 第一次访问key=18（不存在） cout << diffMap[18] << endl; // 输出：0（自动插入18:0） diffMap[18]++; cout << diffMap[18] << endl; // 输出：1（value被修改） // 第二次访问key=18（存在） cout << diffMap[18] << endl; // 输出：1 diffMap[18]++; cout << diffMap[18] << endl; // 输出：2 return 0; }

运行这段代码，你会看到unordered_map自动处理了 key 的插入和 value 的初始化。

总结

1. 可以直接用[]定义键值对：unordered_map的[]运算符会自动检查 key 是否存在，不存在则插入并初始化 value 为类型默认值（int是 0），存在则返回对应 value 的引用。
2. 你的代码用法是最优的：在统计次数的场景中，直接使用diffMap[diff]是最简洁的写法，无需额外的find或insert操作。
3. 区别于find：如果只是想读取 key 的值而不想插入，可用find方法；如果需要插入并修改，[]运算符更高效。