侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

【暴力, 枚举】最大公因数等于 K 的子数组数目【力扣第 316 场周赛】

GabrielxD
2022-10-23 / 0 评论 / 0 点赞 / 259 阅读 / 488 字
温馨提示:
本文最后更新于 2022-11-04,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

6224. 最大公因数等于 K 的子数组数目


给你一个整数数组 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

  • 判断长度为一的子数组时:该元素的最大公因数是他本身。
  • 判断长度大于一的子数组时:先求出前两个元素的最大公因数(tmp),然后遍历该数组,把每个元素与之前求出的 tmp 求最大公因数,并把 tmp 维护为最小的最大公因数,遍历完成之后判断 tmp 是否等于 k 即可。

代码

class Solution {
    public int subarrayGCD(int[] nums, int k) {
        int cnt = 0, n = nums.length;
        for (int len = 1; len <= n; ++len) {
            outer: for (int i = 0; i <= n - len; ++i) {
                if (len == 1) {
                    if (nums[i] == k) ++cnt;
                    continue;
                }
                int tmp = gcd(nums[i], nums[i + 1]);
                for (int j = i; j < i + len; ++j) {
                    int tmp2 = gcd(tmp, nums[j]);
                    if (tmp2 < k) continue outer;
                    tmp = Math.min(tmp, tmp2);
                }
                if (tmp == k) ++cnt;
            }
        }
        return cnt;
    }
    
    int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}
0

评论区