[LeetCode] 1814. Count Nice Pairs in an Array

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.

Example 1:

Input: nums = [42,11,1,97]
Output: 2
Explanation: The two pairs are:
 - (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.

Example 2:

Input: nums = [13,10,35,24,76]
Output: 4

Constraints:

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 109

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

给你一个数组 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 取余 后返回。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/count-nice-pairs-in-an-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这道题思路类似 two sum。注意题目描述，题目让你找的是有多少对下标（i, j）满足 nums[i] + rev(nums[j]) == nums[j] + rev(nums[i])，其中 rev() 函数是把这个数字翻转过来。

这个题目很像 two sum，也是找两数之和，只不过等号右边也是两数之和。我们可以把这个等式转换成 nums[i] - rev(nums[i]) == nums[j] - rev(nums[j])，这样我们找的就是是否存在两个不同的下标，对应的两个数字的 nums[i] - rev(nums[i]) 相等。这里为了保险起见，计算结果我用了 long 型避免溢出。

时间O(n * logC) - rev()函数的复杂度是 logC

空间O(n)

Java实现

 1 class Solution {
 2     public int countNicePairs(int[] nums) {
 3         int MOD = (int) Math.pow(10, 9) + 7;
 4         long count = 0;
 5         HashMap<Integer, Integer> map = new HashMap<>();
 6         for (int num : nums) {
 7             int rev = helper(num);
 8             if (map.containsKey(num - rev)) {
 9                 count += map.get(num - rev);
10             }
11             map.put(num - rev, map.getOrDefault(num - rev, 0) + 1);
12         }
13         return (int) (count % MOD);
14     }
15     
16     private int helper(int num) {
17         int res = 0;
18         while (num != 0) {
19             res = res * 10 + num % 10;
20             num /= 10;
21         }
22         return res;
23     }
24 }

two sum题目总结

LeetCode 题目总结