Easy

题目描述

给你两个正整数 low 和 high。

对于一个由 2 * n 位数字组成的整数 x，如果其前 n 位数字的和等于后 n 位数字的和，那么这个整数就是对称的。奇数位数的数字永远不对称。

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

示例 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

解题思路

解题思路

这道题要求我们找到指定范围内的对称整数。根据题目定义，对称整数必须满足：

  1. 位数为偶数（2*n位）
  2. 前n位数字之和等于后n位数字之和

方法分析

暴力枚举法（推荐）： 由于数据范围较小（high <= 10^4），我们可以直接遍历范围内的每个数字，检查是否为对称整数。

具体步骤：

  1. 遍历 [low, high] 范围内的每个数字
  2. 将数字转换为字符串，检查位数是否为偶数
  3. 如果是偶数位，计算前半部分数字之和和后半部分数字之和
  4. 如果两个和相等，则该数字是对称整数，计数器加1

这种方法的优点是实现简单直观，时间复杂度在给定约束下完全可以接受。

优化思路： 由于约束条件限制了high <= 10^4，最多只有4位数，可能的对称整数形式有限：

  • 2位数：AB形式，需要A=B
  • 4位数：ABCD形式，需要A+B=C+D

但考虑到代码简洁性和通用性，直接枚举更加清晰。

代码实现

class Solution {
public:
    int countSymmetricIntegers(int low, int high) {
        int count = 0;
        
        for (int num = low; num <= high; num++) {
            string s = to_string(num);
            int n = s.length();
            
            // 奇数位数不能是对称整数
            if (n % 2 == 1) continue;
            
            int half = n / 2;
            int leftSum = 0, rightSum = 0;
            
            // 计算前半部分和后半部分的数字之和
            for (int i = 0; i < half; i++) {
                leftSum += s[i] - '0';
                rightSum += s[i + half] - '0';
            }
            
            if (leftSum == rightSum) {
                count++;
            }
        }
        
        return count;
    }
};

class Solution:
    def countSymmetricIntegers(self, low: int, high: int) -> int:
        count = 0
        
        for num in range(low, high + 1):
            s = str(num)
            n = len(s)
            
            # 奇数位数不能是对称整数
            if n % 2 == 1:
                continue
            
            half = n // 2
            left_sum = sum(int(digit) for digit in s[:half])
            right_sum = sum(int(digit) for digit in s[half:])
            
            if left_sum == right_sum:
                count += 1
        
        return count

public class Solution {
    public int CountSymmetricIntegers(int low, int high) {
        int count = 0;
        
        for (int num = low; num <= high; num++) {
            string s = num.ToString();
            int n = s.Length;
            
            // 奇数位数不能是对称整数
            if (n % 2 == 1) continue;
            
            int half = n / 2;
            int leftSum = 0, rightSum = 0;
            
            // 计算前半部分和后半部分的数字之和
            for (int i = 0; i < half; i++) {
                leftSum += s[i] - '0';
                rightSum += s[i + half] - '0';
            }
            
            if (leftSum == rightSum) {
                count++;
            }
        }
        
        return count;
    }
}

var countSymmetricIntegers = function(low, high) {
    let count = 0;
    
    for (let i = low; i <= high; i++) {
        const str = i.toString();
        const len = str.length;
        
        if (len % 2 === 0) {
            const mid = len / 2;
            let leftSum = 0;
            let rightSum = 0;
            
            for (let j = 0; j < mid; j++) {
                leftSum += parseInt(str[j]);
                rightSum += parseInt(str[j + mid]);
            }
            
            if (leftSum === rightSum) {
                count++;
            }
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O((high - low + 1) × log(high))，其中 log(high) 表示数字位数，需要遍历每个数字并处理其每一位
空间复杂度O(log(high))，用于存储数字的字符串表示

相关题目