Medium

题目描述

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 nums 的子数组中元素的最大公约数等于 k 的子数组数目。

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

数组的 最大公约数 是能整除数组中所有元素的最大正整数。

示例 1：

输入：nums = [9,3,1,2,6,3], k = 3
输出：4
解释：nums 的子数组中，满足元素的最大公约数等于 3 的子数组如下：
- [9,3,1,2,6,3]
- [9,3,1,2,6,3] 
- [9,3,1,2,6,3]
- [9,3,1,2,6,3]

示例 2：

输入：nums = [4], k = 7
输出：0
解释：不存在满足元素的最大公约数等于 7 的子数组。

提示：

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

解题思路

这道题要求找到所有最大公约数等于 k 的子数组数目。由于数组长度较小（最多 1000），我们可以采用暴力枚举的方法。

解题思路：

  1. 暴力枚举：枚举所有可能的子数组，计算每个子数组的最大公约数，统计等于 k 的数量。

  2. 优化的枚举：对于每个起始位置 i，我们从 i 开始向右扩展子数组。关键观察是，当我们从位置 i 到 j 的子数组的最大公约数已经小于 k 时，继续扩展也不可能得到等于 k 的最大公约数，因为最大公约数只会越来越小。

  3. 早期剪枝：

    • 如果当前元素不能被 k 整除，那么包含这个元素的任何子数组的最大公约数都不可能是 k
    • 如果当前子数组的最大公约数已经小于 k，则停止扩展

算法步骤：

  1. 遍历每个可能的起始位置 i
  2. 从位置 i 开始，逐步扩展子数组到位置 j
  3. 计算当前子数组的最大公约数
  4. 如果等于 k，计数器加1
  5. 如果小于 k，停止扩展（剪枝）
  6. 返回总计数

时间复杂度主要由计算最大公约数决定，使用欧几里得算法可以高效计算。

代码实现

class Solution {
public:
    int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
    
    int subarrayGCD(vector<int>& nums, int k) {
        int n = nums.size();
        int count = 0;
        
        for (int i = 0; i < n; i++) {
            if (nums[i] % k != 0) continue; // 剪枝：如果当前数不能被k整除
            
            int currentGCD = 0;
            for (int j = i; j < n; j++) {
                if (nums[j] % k != 0) break; // 剪枝：如果当前数不能被k整除
                
                currentGCD = gcd(currentGCD, nums[j]);
                
                if (currentGCD == k) {
                    count++;
                } else if (currentGCD < k) {
                    break; // 剪枝：GCD已经小于k，不可能再等于k
                }
            }
        }
        
        return count;
    }
};

class Solution:
    def subarrayGCD(self, nums: List[int], k: int) -> int:
        import math
        
        n = len(nums)
        count = 0
        
        for i in range(n):
            if nums[i] % k != 0:  # 剪枝：如果当前数不能被k整除
                continue
                
            current_gcd = 0
            for j in range(i, n):
                if nums[j] % k != 0:  # 剪枝：如果当前数不能被k整除
                    break
                    
                current_gcd = math.gcd(current_gcd, nums[j])
                
                if current_gcd == k:
                    count += 1
                elif current_gcd < k:
                    break  # 剪枝：GCD已经小于k，不可能再等于k
        
        return count

public class Solution {
    private int GCD(int a, int b) {
        return b == 0 ? a : GCD(b, a % b);
    }
    
    public int SubarrayGCD(int[] nums, int k) {
        int n = nums.Length;
        int count = 0;
        
        for (int i = 0; i < n; i++) {
            if (nums[i] % k != 0) continue; // 剪枝：如果当前数不能被k整除
            
            int currentGCD = 0;
            for (int j = i; j < n; j++) {
                if (nums[j] % k != 0) break; // 剪枝：如果当前数不能被k整除
                
                currentGCD = GCD(currentGCD, nums[j]);
                
                if (currentGCD == k) {
                    count++;
                } else if (currentGCD < k) {
                    break; // 剪枝：GCD已经小于k，不可能再等于k
                }
            }
        }
        
        return count;
    }
}

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

复杂度分析

复杂度类型分析
时间复杂度O(n² × log(max(nums)))
空间复杂度O(1)

时间复杂度分析：

  • 外层循环：O(n)
  • 内层循环：最坏情况 O(n)
  • GCD 计算：O(log(max(nums)))
  • 由于剪枝优化，实际运行时间会更好

空间复杂度分析：

  • 只使用了常数个额外变量

相关题目