【LeetCode】【Java】 最小公倍数为 K 的子数组数目

2470. 最小公倍数为 K 的子数组数目 - 力扣（Leetcode）

标题 题意：

题目给出了两个关键条件，求最小公倍数，求子数组，明确问题，接下来就是求解了

思路:

一开始我被困扰在求子数组上了，其实利用两个for循环就可以解决，至于最小公倍数的求解，可以通过求最大公约数间接求最小公倍数。

求最小公倍数：
由于两个数的乘积等于这两个数的最大公约数与最小公倍数的积。即（a，b）×[a，b]=a×b。所以，求两个数的最小公倍数，就可以先求出它们的最大公约数，然后用上述公式求出它们的最小公倍数。

最小公倍数tp = num1 * num2 / 最大公约数

可以通过这个公式来求出最小公倍数，最大公约数的求解方式可以通过辗转相除法（欧几里得法最大公约数_百度百科 (baidu.com)）。

求的的最小公倍数tp有三种可能

tp == k 结果加一

tp > k 不符合条件

tp < k 只有当前子数组的第一个元素可能出现该情况，最小公倍数不是k，但是可能和后续元素一起可能构成最小公倍数，需要跳过。

求子数组：

外层for循环是确定每次遍历的起始位置i，内层for循环是求从i开始的所有子数组，相当于是不断更新左边界，用[3,6,2,7,1]举例

当遍历中，在连续的子数组中，有一个数不符合后，就跳出内循环，从起始位置i的下一个元素开始，因为要求是连续的子数组的最小公倍数为k。而且由于是从左开始计算，当前元素满足条件时，如果下一个也满足，那么就可以直接在结果上增加1，有点滑动窗口的感觉。

代码

class Solution {
    public int subarrayLCM(int[] nums, int k) {
        int len = nums.length;
        int res = 0;
        for (int i=0; i<len; i++) {
            int tp = nums[i];
            for (int j=i; j<len; j++) {
                //最小公倍数 = a * b /最大公约数
                tp = tp * nums[j] / gcd(nums[j],tp);
                System.out.println(i+" "+j+" "+tp);
                if (tp == k) {
                    res ++;
                } else if (tp > k) {
                    break;  //不满足的条件，最小公倍数大于k，那么后续元素将无法组成最小公倍数为k
                }
            }
        }
        return res;
    }
    public int gcd(int a,int b) {
        //辗转相除法
        while(b!=0) {
            int tp = a % b;
            a = b;
            b = tp;
        }
        return a;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29