Easy

题目描述

非零整数是在其十进制表示中不包含任何 0 的正整数。

给定一个整数 n，返回一个包含两个整数 [a, b] 的列表，其中：

  • a 和 b 都是非零整数
  • a + b = n

测试用例保证至少存在一个有效解。如果有多个有效解，你可以返回其中任何一个。

示例 1：

输入：n = 2
输出：[1,1]
解释：设 a = 1，b = 1。
a 和 b 都是非零整数，且 a + b = 2 = n。

示例 2：

输入：n = 11
输出：[2,9]
解释：设 a = 2，b = 9。
a 和 b 都是非零整数，且 a + b = 11 = n。
注意还有其他有效答案如 [8, 3] 也是可以接受的。

约束：

  • 2 <= n <= 10^4

提示：

  • 循环遍历从 1 到 n 的所有元素
  • 选择 A = i 和 B = n - i，然后检查 A 和 B 是否都是非零整数

解题思路

这道题的核心是找到两个不含 0 的正整数，使它们的和等于给定的 n。

解法分析：

  1. 暴力枚举法（推荐）：从 1 开始遍历，对于每个数字 i，计算 j = n - i，然后检查 i 和 j 是否都不含数字 0。这是最直观的解法，由于 n 的范围较小（≤ 10^4），时间复杂度完全可以接受。

  2. 优化思路：可以考虑从较小的数开始枚举，一旦找到符合条件的组合就立即返回，平均情况下会更快。

实现要点：

  • 需要一个辅助函数来判断一个数是否包含 0
  • 可以通过对数字取余和除法来逐位检查
  • 也可以将数字转为字符串检查是否包含字符 ‘0’

由于题目保证至少存在一个解，我们只需要找到第一个满足条件的组合即可。数字较小时通常能很快找到解，比如对于大部分情况，a = 1 或 a = 2 就能找到合适的 b。

代码实现

class Solution {
public:
    vector<int> getNoZeroIntegers(int n) {
        for (int a = 1; a < n; a++) {
            int b = n - a;
            if (hasNoZero(a) && hasNoZero(b)) {
                return {a, b};
            }
        }
        return {};
    }
    
private:
    bool hasNoZero(int num) {
        while (num > 0) {
            if (num % 10 == 0) return false;
            num /= 10;
        }
        return true;
    }
};

class Solution:
    def getNoZeroIntegers(self, n: int) -> List[int]:
        def has_no_zero(num):
            return '0' not in str(num)
        
        for a in range(1, n):
            b = n - a
            if has_no_zero(a) and has_no_zero(b):
                return [a, b]
        
        return []

public class Solution {
    public int[] GetNoZeroIntegers(int n) {
        for (int a = 1; a < n; a++) {
            int b = n - a;
            if (HasNoZero(a) && HasNoZero(b)) {
                return new int[] {a, b};
            }
        }
        return new int[0];
    }
    
    private bool HasNoZero(int num) {
        while (num > 0) {
            if (num % 10 == 0) return false;
            num /= 10;
        }
        return true;
    }
}

/**
 * @param {number} n
 * @return {number[]}
 */
var getNoZeroIntegers = function(n) {
    const hasNoZero = (num) => {
        return !num.toString().includes('0');
    };
    
    for (let a = 1; a < n; a++) {
        let b = n - a;
        if (hasNoZero(a) && hasNoZero(b)) {
            return [a, b];
        }
    }
    
    return [];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n × log n)最坏情况需要遍历 n-1 次，每次检查数字是否含 0 需要 O(log n) 时间
空间复杂度O(1)只使用常数额外空间