Leetcode 2447. Number of Subarrays With GCD Equal to K

[Woodyiiiiiii]

这道题我一开始想用滑动窗口的方法去做，但写的时候想到，没有能够让左边界滑动的条件，再加上条件里数组长度并不是很长(暗示)，所以放弃了此法(可以想到，遇到方法定式，要学会在关键处判断并及时转换思想)。

那么如果用O(n^2)的方法遍历所有子数组，那么如果计算子数组的最大公约数呢？虽然用Copilot提示过了，但细想下，最大公约数以最小的数为基准，每次增加一个数，最大公约数只可能变小，不会变大...

class Solution {
    public int subarrayGCD(int[] nums, int k) {
        
        int res = 0;
        int n = nums.length;

        for (int i = 0; i < n; i++) {
            if (nums[i] == k) {
                res++;
            }
            int gcd = nums[i];
            for (int j = i + 1; j < n; j++) {
                gcd = gcd(gcd, nums[j]);
                if (gcd == k) {
                    res++;
                }
            }
        }

        return res;
        
    }
    
    // 求最大公约数gcd
    public int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
    
}

---

• https://leetcode.com/problems/number-of-subarrays-with-gcd-equal-to-k/