LeetCode 题解工作台
最小公倍数等于 K 的子数组数目
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 nums 的 子数组 中满足 元素最小公倍数为 k 的子数组数目。 子数组 是数组中一个连续非空的元素序列。 数组的最小公倍数 是可被所有数组元素整除的最小正整数。 示例 1 ： 输入： nums = [3,6,2,7,1], k = 6…
3
题型
4
代码语言
3
相关题
当前训练重点
中等 · 数组·数学
答案摘要
枚举每个数作为子数组的第一个数，然后枚举每个数作为子数组的最后一个数，计算这个子数组的最小公倍数，如果最小公倍数等于 ，则答案加一。 时间复杂度 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·数学 题型思路
题目描述
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 nums 的 子数组 中满足 元素最小公倍数为 k 的子数组数目。
子数组 是数组中一个连续非空的元素序列。
数组的最小公倍数 是可被所有数组元素整除的最小正整数。
示例 1 ：
输入：nums = [3,6,2,7,1], k = 6 输出：4 解释：以 6 为最小公倍数的子数组是： - [3,6,2,7,1] - [3,6,2,7,1] - [3,6,2,7,1] - [3,6,2,7,1]
示例 2 ：
输入：nums = [3], k = 2 输出：0 解释：不存在以 2 为最小公倍数的子数组。
提示：
1 <= nums.length <= 10001 <= nums[i], k <= 1000
解题思路
方法一：枚举
枚举每个数作为子数组的第一个数，然后枚举每个数作为子数组的最后一个数，计算这个子数组的最小公倍数，如果最小公倍数等于 ，则答案加一。
时间复杂度 。
class Solution:
def subarrayLCM(self, nums: List[int], k: int) -> int:
n = len(nums)
ans = 0
for i in range(n):
a = nums[i]
for b in nums[i:]:
x = lcm(a, b)
ans += x == k
a = x
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Ensure the candidate is familiar with the properties of the least common multiple and its efficient calculation.
- question_mark
Watch for optimization approaches and the candidate's awareness of trade-offs between brute force and optimized solutions.
- question_mark
Evaluate how well the candidate adapts their approach based on problem constraints, especially in terms of optimizing subarray checks.
常见陷阱
外企场景- error
Failing to optimize the LCM computation by recalculating it for every subarray from scratch.
- error
Not accounting for early termination when the running LCM exceeds k.
- error
Misunderstanding the problem by assuming any number divisible by k is valid, when the LCM of the subarray must exactly equal k.
进阶变体
外企场景- arrow_right_alt
What if the array size is larger than the given constraints?
- arrow_right_alt
How would this problem change if negative numbers were allowed in the array?
- arrow_right_alt
What if instead of LCM, we needed to check for the greatest common divisor (GCD) of subarrays instead?