点击获取AI摘要

2843. 统计对称整数的数目 E

给你两个正整数 low 和 high 。

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

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

示例 1：

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

示例 2：

1
2
3
输入：low = 1200, high = 1230
输出：4
解释：在 1200 到 1230 范围内共有 4 个对称整数：1203、1212、1221 和 1230 。
  • 提示：1<=low<=high<=1041 <= low <= high <= 10^4

题目需要找出在给定范围内满足特定数字对称条件的所有整数的数量。

  1. 检查位数是否为偶数：只有当数字的位数是偶数时才有可能成为对称整数，否则直接跳过。
  2. 分割数字前后半部分：对于一个 2*n 位数字，将该数字转换为字符串，然后将其前 n 位数字和后 n 位数字分别累加求和，判断两部分是否相等。两者之和相等，则该数字符合条件。
  3. 遍历范围： low 和 high 的范围较小（最高 10410^4），可以直接遍历 [low, high] 区间内的所有数字，对符合条件的数字进行计数。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def countSymmetricIntegers(self, low: int, high: int) -> int:
        count = 0
        for num in range(low, high + 1):
            num_str = str(num)
            # 数字必须为偶数位，才能分成两部分比较
            if len(num_str) % 2 == 0:
                half = len(num_str) // 2
                # 将前一半和后一半的各个数字相加
                left_sum = sum(int(digit) for digit in num_str[:half])
                right_sum = sum(int(digit) for digit in num_str[half:])
                if left_sum == right_sum:
                    count += 1
        return count
  • 首先通过 str(num) 将整数转换为字符串，以便判断数字的位数是否为偶数。
  • 如果是偶数位，则将字符串分为前后两部分，分别计算各自数字的和。
  • 如果两部分的和相等，则计数器 count 累加。

通过遍历 [𝑙𝑜𝑤,ℎ𝑖𝑔ℎ]范围内的每个整数，对于每个数字：

  1. 将数字转换为字符串：复杂度 O(d)O(d)（其中 ddd 为数字的位数）。
  2. 对前半部分和后半部分求和，各需要 O(d/2)O(d/2)，加起来也是 O(d)O(d)。

总体时间复杂度大致为 O(N×d)O(N×d)，其中 N=high−low+1N=high−low+1，dd通常为常数