0086.近似GCD.md

86. 近似GCD

题目链接

双指针

题意：

我们需要找的子数组需要满足以下两个条件:

• 数组中最多只有一个元素和 g 的最大公约数不等于 g ，其余的最大公约数都等于 g
• 数组的长度大于等于 2

使用双指针法，定义左指针 j 和右指针 i 分别表示：下标以 i 结尾，j ~ i-1开头的子数组都满足条件。

具体步骤如下:

1. 初始化 j = 0，last = -1。last用于维护记录最新的与 g 最大公约数不为 g 的下标
2. 遍历数组 nums 当遇到nums[i] % g != 0时更新 last 和 j
3. 累加结果

需要注意的点:

• last 初始化为 -1 的目的是为了满足题意"可以更改数组中的一个元素"
• 每次遍历结果累加(左指针 - 右指针)即可，不需要判断数组长度是否不小于2
• nums[i] % g != 0是用于判断 nums[i] 和 g 的最大公约数是否等于 g

C

C++

// 双指针 时间复杂度: O(n)
#include <iostream>
using namespace std;
int main()
{
    int n, g;
    cin >> n >> g;
    int nums[n];
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    int last = -1, j = 0;
    long res = 0;
    for (int i = 0; i < n; i++) {
        if (nums[i] % g != 0) {
            j = last + 1;  // 左指针更新
            last = i;  // 记录当前右指针位置
        }
        res += (i-j);
    }
    cout << res << endl;
    return 0;
}

Java

// 双指针 时间复杂度: O(n)
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        long g = scan.nextLong();
        long[] nums = new long[n];
        for (int i = 0; i < n; i++) {
            nums[i] = scan.nextLong();
        }
        int last = -1, j = 0;
        long res = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] % g != 0) {
                j = last + 1;  // 左指针更新
                last = i;  // 记录当前右指针位置
            }
            res += (i-j);
        }
        System.out.println(res);
        scan.close();
    }
}

Python

JS

Go