2269-找到一个数字的 K 美丽值

一个整数 num 的 **k **美丽值定义为 num 中符合以下条件的 子字符串 数目：

• 子字符串长度为 k 。
• 子字符串能整除 num 。

给你整数 num 和 k ，请你返回 _ _num 的 k 美丽值。

注意：

• 允许有 前缀 0 。
• 0 不能整除任何值。

一个 子字符串 是一个字符串里的连续一段字符序列。

示例 1：

**输入：** num = 240, k = 2
**输出：** 2
**解释：** 以下是 num 里长度为 k 的子字符串：
- " _ **24**_ 0" 中的 "24" ：24 能整除 240 。
- "2 _ **40**_ " 中的 "40" ：40 能整除 240 。
所以，k 美丽值为 2 。

示例 2：

**输入：** num = 430043, k = 2
**输出：** 2
**解释：** 以下是 num 里长度为 k 的子字符串：
- " _ **43**_ 0043" 中的 "43" ：43 能整除 430043 。
- "4 _ **30**_ 043" 中的 "30" ：30 不能整除 430043 。
- "43 _ **00**_ 43" 中的 "00" ：0 不能整除 430043 。
- "430 _ **04**_ 3" 中的 "04" ：4 不能整除 430043 。
- "4300 _ **43**_ " 中的 "43" ：43 能整除 430043 。
所以，k 美丽值为 2 。

提示：

• 1 <= num <= 109
• 1 <= k <= num.length （将 num 视为字符串）

方法一：枚举

思路与算法

为了方便起见，我们用 s 表示 num 对应十进制表示的字符串。我们可以从左至右枚举 s 中长度为 k 的字符串，并判断该子串对应的整数能否被 num 整除。与此同时，我们用 res 统计能被 num 整除的子串数量，如果某个子串能被 num 整除，则我们将 res 加上 1。最终，res 即为 num 的 k 美丽值，我们返回 res 作为答案。

代码

[sol1-C++]

class Solution {
public:
    int divisorSubstrings(int num, int k) {
        string s = to_string(num);   // num 十进制表示字符串
        int n = s.size();
        int res = 0;
        for (int i = 0; i <= n - k; ++i) {
            // 枚举所有长度为 k 的子串
            int tmp = stoi(s.substr(i, k));
            if (tmp && num % tmp == 0) {
                ++res;
            }
        }
        return res;
    }
};

[sol1-Python3]

class Solution:
    def divisorSubstrings(self, num: int, k: int) -> int:
        s = str(num)   # num 十进制表示字符串
        n = len(s)
        res = 0
        for i in range(n - k + 1):
            # 枚举所有长度为 k 的子串
            tmp = int(s[i:i+k])
            if tmp != 0 and num % tmp == 0:
                res += 1
        return res

复杂度分析

• 时间复杂度：O(nk)，其中 n 为 num 的位数, k 为子串的长度。我们总共需要枚举 O(n) 个子串，其中判断每个子串都需要 O(k) 的时间复杂度。

• 空间复杂度：O(n)，即为辅助字符串的空间开销。