代码编织梦想

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

难度:中等

给你一个数组 nums ,数组中只包含非负整数。定义 rev(x) 的值为将整数 x 各个数字位反转得到的结果。比方说 rev(123) = 321rev(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

哈希表

思路:
首先题目给出一个下标从 0 0 0 开始长度为 n n n 的非负整数数组 nums \textit{nums} nums,并给出「好下标对」的定义——对于某一个下标对 ( i , j ) (i,j) (i,j) 0 ≤ i < j < n 0 \le i < j < n 0i<j<n,若满足:

nums [ i ] + rev ( nums [ j ] ) = nums [ j ] + rev ( nums [ i ] ) (1) \textit{nums}[i] + \textit{rev}(\textit{nums}[j]) = \textit{nums}[j] + \textit{rev}(\textit{nums}[i]) \tag{1} nums[i]+rev(nums[j])=nums[j]+rev(nums[i])(1)

则该下标对为「好下标对」。现在我们设: f ( i ) = nums [ i ] − rev ( nums [ i ] ) f(i) = \textit{nums}[i] - \textit{rev}(\textit{nums}[i]) f(i)=nums[i]rev(nums[i]),则表达式 ( 1 ) (1) (1) 可以等价于:

f ( i ) = f ( j ) (2) f(i) = f(j) \tag{2} f(i)=f(j)(2)

那么我们从左到右遍历数组 nums \textit{nums} nums,并在遍历的过程用「哈希表」统计每一个位置 i i i 0 ≤ i < n 0 \le i < n 0i<n f ( i ) f(i) f(i) 的个数,则对于位置 j j j 0 ≤ j < n 0 \le j < n 0j<n,以 j j j 结尾的「好下标对」的个数为此时「哈希表」中 f ( j ) f(j) f(j) 的数目。那么我们只需要在遍历时同时统计以每一个位置为结尾的「好下标对」数目即可。

复杂度分析:

  • 时间复杂度: O ( n × log ⁡ C ) O(n \times \log C) O(n×logC),其中 n n n 为数组 nums \textit{nums} nums 的长度, C C C 为数组 nums \textit{nums} nums 中的数字范围。其中 O ( log ⁡ C ) O(\log C) O(logC) 为反转数位的时间复杂度。
  • 空间复杂度: O ( n ) O(n) O(n),其中 n n n 为数组 nums \textit{nums} nums 的长度,主要为哈希表的空间开销。
class Solution:
    def countNicePairs(self, nums: List[int]) -> int:
        diff_count, res = dict(), 0
        for i in nums:
            diff = i - int(str(i)[::-1])
            if diff_count.get(diff):
                res += diff_count[diff]
                diff_count[diff] += 1
            else:
                diff_count[diff] = 1
        return res % (10 ** 9 + 7)

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/count-nice-pairs-in-an-array

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_45616285/article/details/128718472

算法--06年华为面试:求两个数组的最小差值(java实现)-爱代码爱编程

Q题目 华为06年面试题(要求8分钟完成) 有两个数组a,b,大小都为n,数组元素的值任意,无序; 要求:通过交换a,b中的元素,使数组a元素的和与数组b元素的和之间的差最小。 A解法 1.常见错误逻辑

算法刷题(11)--统计一个数字在排序数组中出现的次数。_guozhu_zhu的博客-爱代码爱编程

算法刷题(11)--统计一个数字在排序数组中出现的次数。 方法一:(暴力破解) package p2; /** * 题目描述: * 统计一个数字在排序数组中出现的次数。 * @author Guozhu Zhu * @date 2018/4/25 * @version 1.0 * */ public class Test01 { p

java算法:在给定的数组中查找出现次数最多的元素(java版本)_梅森上校的博客-爱代码爱编程_java数组中出现次数最多的元素

JAVA算法:在给定的数组中查找出现次数最多的元素(JAVA版本) 题目要求:在给定的数组中查找出现次数最多的元素,以及其出现的次数。 例如:在数组 { 2, 3, 1, 2, 2, 5, 6, 8, 2, 3, 2, 4, 2 }中,元素2出现的次数最多,一共出现了 6次。 问题分析 对于这个问题,要求的结果是找到出现次数最多的元素,以及其出现

算法:求多个数组的排列组合_superavalon的博客-爱代码爱编程_求多个数组的组合数的方法

问题: 给到如下数组: $fields[0] = ["ddd"]; $fields[1] = ["eee","ffff","ccc"]; $fields[2] = ["gggg","hhh"]; $fields[3] = ["aaa","bbb"]; 求他们的所有排列组合结果,比如: ddd  eee  gggg  aaa ddd  eee 

java数据结构与算法刷题-----LeetCode448:找到所有数组中消失的数字-爱代码爱编程

java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完):https://blog.csdn.net/grd_java/article/details/123063846 思路分析 数组nums有n个元素,这些元素的取值范围是[1,n],我们需要找出[1,n]中没有出

c语言经典算法实例1:求二维数组最大最小值_编程爱好者-阿新的博客-爱代码爱编程

C语言经典算法实例1:求二维数组最大最小值 一、问题描述二、算法实例编译环境三、算法实例实现过程3.1、包含头文件3.2、定义宏和声明数组3.3、声明相关变量3.3、输入数组(方阵)的阶3.4、输出 “输入的数组”3

javascript算法07-统计一致字符串的数目_三七有星辰的博客-爱代码爱编程

一、问题描述 给你一个由不同字符组成的字符串allowed和一个字符串数组words。如果一个字符串的每一个字符都在allowed中,就称这个字符串是一致字符串。 请你返回words数组中一致字符串的数目。 示例1: 输