文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

給你一個數(shù)組 nums ，數(shù)組中只包含非負(fù)整數(shù)。
定義 rev(x) 的值為將整數(shù) x 各個數(shù)字位反轉(zhuǎn)得到的結(jié)果。
比方說 rev(123) = 321 ， rev(120) = 21 。我們稱滿足下面條件的下標(biāo)對 (i, j) 是 好的 ：

• 0 <= i < j < nums.length
• nums[i] + rev(nums[j]) == nums[j] + rev(nums[i])

請你返回好下標(biāo)對的數(shù)目。由于結(jié)果可能會很大，請將結(jié)果對 10^9 + 7 取余 后返回。

示例 1： 輸入：nums = [42,11,1,97] 輸出：2 解釋：兩個坐標(biāo)對為：- (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^5 0 <= nums[i] <= 10^9

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/count-nice-pairs-in-an-array
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

2. 解題

• 條件等價于 nums[i] - rev(nums[i]) == nums[j] - rev(nums[j])
• 使用 nums[i] - rev(nums[i]) 作為哈希的 key， 計算數(shù)量
• 每個key內(nèi)的組合都可以，$C_n^2$

class Solution { public:int countNicePairs(vector<int>& nums) {long long n = nums.size(), ans = 0, mod = 1e9+7;;map<int, long long> m;for(int i = 0; i < n; i++) {int n = nums[i], rev = 0;while(n){rev = rev*10 + n%10;n /= 10;}m[nums[i]-rev]++;}for(auto it = m.begin(); it != m.end(); ++it){ans = (ans + it->second*(it->second-1)/2)%mod;}return ans;} };

120 ms 44.2 MB C++

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關(guān)注我的公眾號（Michael阿明），一起加油、一起學(xué)習(xí)進步！

總結(jié)

以上是生活随笔為你收集整理的LeetCode 1814. 统计一个数组中好对子的数目（哈希）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。