当前位置：首页 > news >正文

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

news 来源：原创 2024/11/13 9:38:53

来源：力扣（LeetCode）

描述：

给你一个数组 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])

请你返回好下标对的数目。由于结果可能会很大，请将结果对 10⁹ + 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⁵
0 <= nums[i] <= 10⁹

方法：哈希表

思路与算法

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

nums[i] + rev(nums[j]) = nums[j] + rev(nums[i]) (1)

则该下标对为「好下标对」。现在我们设：f(i) = nums[i] − rev(nums[i])，则表达式 (1) 可以等价于：

f(i) = f(j) (2)

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

代码：

class Solution {
public:
    int countNicePairs(vector<int>& nums) {
        const int MOD = 1000000007;
        int res = 0;
        unordered_map<int, int> h;
        for (int i : nums) {
            int temp = i, j = 0;
            while (temp > 0) {
                j = j * 10 + temp % 10;
                temp /= 10;
            }
            res = (res + h[i - j]) % MOD;
            h[i - j]++;
        }
        return res;
    }
};

执行用时：96 ms, 在所有 C++ 提交中击败了84.09%的用户
内存消耗：55.3 MB,在所有 C++ 提交中击败了96.59%的用户
复杂度分析
时间复杂度：O(n×logC)，其中 n 为数组 nums 的长度，C 为数组 nums 中的数字范围。其中 O(logC) 为反转数位的时间复杂度。
空间复杂度：O(n)，其中 n 为数组 nums 的长度，主要为哈希表的空间开销。
author：LeetCode-Solution