[LeetCode] 每日一题 2843. 统计对称整数的数目（简单计数对比）

题目描述

给你两个正整数 low 和 high 。

对于一个由 2 * n 位数字组成的整数 x ，如果其前 n 位数字之和与后 n 位数字之和相等，则认为这个数字是一个对称整数。

返回在 [low, high] 范围内的 对称整数的数目 。

题目链接

https://leetcode.cn/problems/count-symmetric-integers

示例输入

示例 1

输入：low = 1, high = 100
输出：9
解释：在 1 到 100 范围内共有 9 个对称整数：11、22、33、44、55、66、77、88 和 99 。

示例 2

输入：low = 1200, high = 1230
输出：4
解释：在 1200 到 1230 范围内共有 4 个对称整数：1203、1212、1221 和 1230 。

提示

• 1 <= low <= high <= 10^4

解题思路

这道题相比前几天的数位 DP 题来说算是相当“温柔”了😊。题目要求统计在 [low, high] 区间内满足「前一半数字之和等于后一半数字之和」的 对称整数 个数。

这类题一眼就可以想到暴力枚举的方式。我们直接遍历区间内的每一个数，然后判断是否满足对称条件即可。判断方法也不难：先把数字转成字符串，若位数是奇数就直接跳过，否则计算前一半和后一半的数字之和，判断是否相等。

虽然也可以用类似数位 DP 的方式来做（比如预处理从 0 到 x 范围内满足条件的数），但在数据范围不大的前提下，直接暴力统计效率更高，实现也更简单。

代码实现

class Solution {
    public int countSymmetricIntegers(int low, int high) {
        int cnt = 0;
        for (int i = low; i <= high; i++) {
            if (check(i)) {
                cnt++;
            }
        }
        return cnt;
    }

    private boolean check(int num) {
        String s = String.valueOf(num);
        int n = s.length();
        if (n % 2 != 0) {
            return false;
        }
        int helper = 0;
        int len = n >> 1;
        for (int i = 0; i < len; i++) {
            helper += s.charAt(i);
            helper -= s.charAt(i + len);
        }
        return helper == 0;
    }
}

复杂度分析

• 时间复杂度： O(n * log₁₀n)
  其中 n 是区间 [low, high] 的长度，对于每个数字，我们最多遍历它的一半位数

• 空间复杂度： O(1)
  没有使用额外空间，只是基本变量计数

尽管这个复杂度看起来不如数位 DP 高级，但在实际数据量小的题目中，这样的暴力解反而更高效、开发更迅速💡

总结

这题可以说是放松脑子的好机会了——我们直接从逻辑出发，不必考虑复杂的边界压缩或者记忆化搜索之类的优化。作为一道基础的练手题，它也提醒我们有时候“简单直接”就是最优解

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。