【数学, 哈希表, 计数】统计一个数组中好对子的数目

题目

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])

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

解题

方法一：哈希表 数学 计数

思路

好对子需要满足的条件：nums[i] + rev(nums[j]) == nums[j] + rev(nums[i])

这个式子变形一下：nums[i] - rev(nums[i]) == nums[j] - rev(nums[j])

这个题就变成了：【数学, 哈希表, 计数】好数对的数目 ，只不过把对 count(i) 求组合数变成了对 count(nums[i] - rev(nums[i])) 求组合数。

注意数据范围，不用 long long(c++) 或者 long(java) 可能会溢出。

代码

class Solution {
    const int MOD = 1e9 + 7;

    int rev(int x) {
        string str_x = to_string(x);
        reverse(str_x.begin(), str_x.end());
        return stoi(str_x);
    }

public:
    int countNicePairs(vector<int>& nums) {
        unordered_map<int, long long> counts;
        for (int& num : nums) ++counts[num - rev(num)];
        int ans = 0;
        for (auto& [k, v] : counts) ans = (ans + (v * (v - 1) / 2)) % MOD;
        return ans;
    }
};

class Solution {
    private static final int MOD = (int) 1e9 + 7;

    public int countNicePairs(int[] nums) {
        Map<Integer, Long> map = new HashMap<>();
        for (int num : nums) {
            int tmp = num - Integer.parseInt(new StringBuilder(Integer.toString(num)).reverse().toString());
            map.put(tmp, map.getOrDefault(tmp, 0L) + 1);
        }
        int ans = 0;
        for (long count : map.values()) ans = (int) ((ans + (count * (count - 1) / 2)) % MOD);
        return ans;
    }
}

用字符串辅助反转数字未免有点浪费，可以换成取模运算：

class Solution {
    const int MOD = 1e9 + 7;

    int rev(int x) {
        int rev_x = 0;
        while (x) {
            rev_x = rev_x * 10 + x % 10;
            x /= 10;
        }
        return rev_x;
    }

public:
    int countNicePairs(vector<int>& nums) {
        unordered_map<int, long long> counts;
        for (int& num : nums) ++counts[num - rev(num)];
        int ans = 0;
        for (auto& [k, v] : counts) ans = (ans + (v * (v - 1) / 2)) % MOD;
        return ans;
    }
};

class Solution {
    private static final int MOD = (int) 1e9 + 7;

    public int countNicePairs(int[] nums) {
        Map<Integer, Long> map = new HashMap<>();
        for (int num : nums) {
            int diff = num - rev(num);
            map.put(diff, map.getOrDefault(diff, 0L) + 1);
        }
        int ans = 0;
        for (long count : map.values()) ans = (int) ((ans + (count * (count - 1) / 2)) % MOD);
        return ans;
    }

    private int rev(int x) {
        int rev_x = 0;
        while (x != 0) {
            rev_x = rev_x * 10 + x % 10;
            x /= 10;
        }
        return rev_x;
    }
}

用累加的方式求排列数，仅需一次遍历：

class Solution {
    const int MOD = 1e9 + 7;

    int rev(int x) {
        int rev_x = 0;
        while (x) {
            rev_x = rev_x * 10 + x % 10;
            x /= 10;
        }
        
        return rev_x;
    }

public:
    int countNicePairs(vector<int>& nums) {
        unordered_map<int, long long> counts;
        int ans = 0;
        for (int& num : nums) {
            int tmp = num - rev(num);
            long long* count = &counts[tmp];
            ans = (ans + *count) % MOD;
            (*count)++;
        }
        
        return ans;
    }
};

class Solution {
    private static final int MOD = (int) 1e9 + 7;

    public int countNicePairs(int[] nums) {
        Map<Integer, Long> map = new HashMap<>();
        int ans = 0;
        for (int num : nums) {
            int diff = num - rev(num);
            long count = map.getOrDefault(diff, 0L);
            ans = (int) (ans + count) % MOD;
            map.put(diff, count + 1);
        }
        return ans;
    }

    private int rev(int x) {
        int rev_x = 0;
        while (x != 0) {
            rev_x = rev_x * 10 + x % 10;
            x /= 10;
        }
        return rev_x;
    }
}