Medium

题目描述

给你一个整数数组 nums 和一个整数 k，请你统计并返回 nums 的子数组中满足 元素最小公倍数为 k 的子数组数目。

子数组 是数组中一个连续非空的元素序列。

数组的 最小公倍数 是可被数组中所有元素整除的最小正整数。

示例 1：

输入：nums = [3,6,2,7,1], k = 6
输出：4
解释：以 6 为最小公倍数的子数组是：
- [3,6] 从下标 0 到下标 1
- [6] 从下标 1 到下标 1  
- [3,6,2] 从下标 0 到下标 2
- [6,2] 从下标 1 到下标 2

示例 2：

输入：nums = [3], k = 2
输出：0
解释：不存在以 2 为最小公倍数的子数组。

提示：

  • 1 <= nums.length <= 1000
  • 1 <= nums[i], k <= 1000

解题思路

解题思路

这道题要求找出所有最小公倍数等于 k 的连续子数组个数。由于数组长度较小（≤1000），我们可以使用暴力枚举的方法。

核心观察：

  1. 最小公倍数（LCM）具有单调性：随着元素增加，LCM 只会增大或保持不变
  2. 一旦某个子数组的 LCM 超过 k，那么包含这个子数组的更长子数组的 LCM 也不可能等于 k
  3. 如果某个元素不能整除 k，那么包含它的任何子数组的 LCM 都不可能等于 k

算法步骤：

  1. 枚举所有可能的子数组起始位置 i
  2. 从位置 i 开始，逐步扩展子数组终止位置 j
  3. 维护当前子数组的 LCM，如果等于 k 则计数加一
  4. 如果 LCM 超过 k，提前终止内层循环（剪枝优化）

优化技巧：

  • 使用 gcd(a,b) = a*b/lcm(a,b) 和欧几里得算法快速计算 LCM
  • 当 LCM > k 时立即跳出内层循环
  • 预先检查元素是否为 k 的因子，快速过滤无效情况

时间复杂度为 O(n²·log(max(nums)))，空间复杂度为 O(1)。

代码实现

class Solution {
public:
    int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
    
    int lcm(int a, int b) {
        return a / gcd(a, b) * b;
    }
    
    int subarrayLCM(vector<int>& nums, int k) {
        int n = nums.size();
        int count = 0;
        
        for (int i = 0; i < n; i++) {
            int currentLCM = 0;
            for (int j = i; j < n; j++) {
                if (currentLCM == 0) {
                    currentLCM = nums[j];
                } else {
                    currentLCM = lcm(currentLCM, nums[j]);
                }
                
                if (currentLCM == k) {
                    count++;
                } else if (currentLCM > k) {
                    break; // 剪枝：LCM已经超过k，不需要继续扩展
                }
            }
        }
        
        return count;
    }
};

class Solution:
    def subarrayLCM(self, nums: List[int], k: int) -> int:
        def gcd(a, b):
            while b:
                a, b = b, a % b
            return a
        
        def lcm(a, b):
            return a * b // gcd(a, b)
        
        n = len(nums)
        count = 0
        
        for i in range(n):
            current_lcm = 0
            for j in range(i, n):
                if current_lcm == 0:
                    current_lcm = nums[j]
                else:
                    current_lcm = lcm(current_lcm, nums[j])
                
                if current_lcm == k:
                    count += 1
                elif current_lcm > k:
                    break  # 剪枝：LCM已经超过k，不需要继续扩展
        
        return count

public class Solution {
    private int Gcd(int a, int b) {
        return b == 0 ? a : Gcd(b, a % b);
    }
    
    private int Lcm(int a, int b) {
        return a / Gcd(a, b) * b;
    }
    
    public int SubarrayLCM(int[] nums, int k) {
        int n = nums.Length;
        int count = 0;
        
        for (int i = 0; i < n; i++) {
            int currentLCM = 0;
            for (int j = i; j < n; j++) {
                if (currentLCM == 0) {
                    currentLCM = nums[j];
                } else {
                    currentLCM = Lcm(currentLCM, nums[j]);
                }
                
                if (currentLCM == k) {
                    count++;
                } else if (currentLCM > k) {
                    break; // 剪枝：LCM已经超过k，不需要继续扩展
                }
            }
        }
        
        return count;
    }
}

var subarrayLCM = function(nums, k) {
    function gcd(a, b) {
        while (b !== 0) {
            let temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
    
    function lcm(a, b) {
        return (a * b) / gcd(a, b);
    }
    
    let count = 0;
    
    for (let i = 0; i < nums.length; i++) {
        let currentLCM = nums[i];
        
        for (let j = i; j < nums.length; j++) {
            currentLCM = lcm(currentLCM, nums[j]);
            
            if (currentLCM === k) {
                count++;
            } else if (currentLCM > k) {
                break;
            }
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n² · log(max(nums)))双重循环 O(n²)，每次计算 LCM 需要 O(log(max(nums)))
空间复杂度O(1)只使用了常数级别的额外空间

相关题目