【LeetCode】：最长乘积等价子数组【简单】

https://leetcode.cn/problems/maximum-subarray-with-equal-products/description/

以下是解决这道题的详细思路：

一、理解题目要求

1. 题目给定一个由正整数组成的数组 nums，需要找出其中最长的“乘积等价子数组”的长度。
2. 一个数组 arr 被称为“乘积等价数组”，当且仅当 prod(arr) == lcm(arr) * gcd(arr)，其中：
   • prod(arr) 表示 arr 中所有元素的乘积。
   • gcd(arr) 表示 arr 中所有元素的最大公因数（GCD）。
   • lcm(arr) 表示 arr 中所有元素的最小公倍数（LCM）。
3. 子数组是数组中连续的、非空的元素序列。

二、解题方法

1. 暴力解法（遍历所有子数组）

   • 两层循环遍历数组 nums，外层循环 i 从 0 到 nums.length - 1，表示子数组的起始位置。
   • 内层循环 j 从 i 到 nums.length - 1，表示子数组的结束位置。
   • 对于每个子数组 nums[i] 到 nums[j]，计算其 prod（乘积）、gcd（最大公因数）和 lcm（最小公倍数）。
   • 判断是否满足 prod == lcm * gcd，如果满足，更新最长子数组的长度。
   • 时间复杂度：$O(n^3)$，其中 n 是数组 nums 的长度。因为需要遍历所有可能的子数组，对于每个子数组又需要计算 prod、gcd 和 lcm，计算 gcd 和 lcm 的时间复杂度为 $O(n)$，所以总的时间复杂度较高。

2. 优化解法（利用数学性质和滑动窗口）

   • 首先，根据数学性质：对于两个数 a 和 b，有 a * b = gcd(a, b) * lcm(a, b)。推广到多个数，如果一个子数组是“乘积等价子数组”，那么该子数组中任意两个数的乘积也等于它们的 gcd 和 lcm 的乘积。
   • 基于此，我们可以使用滑动窗口的方法。
   • 初始化两个指针 left 和 right 都指向数组的起始位置 0，以及一个变量 maxLen 用于记录最长子数组的长度，初始化为 0。
   • 移动 right 指针，逐步扩大窗口。
   • 在每次移动 right 指针后，计算当前窗口内元素的 prod、gcd 和 lcm。
   • 如果满足 prod == lcm * gcd，则更新 maxLen 为 max(maxLen, right - left + 1)，然后尝试移动 left 指针，缩小窗口，看是否能找到更长的满足条件的子数组。
   • 如果不满足条件，则继续移动 right 指针，扩大窗口。
   • 时间复杂度：$O(n)$，因为每个元素最多被 left 和 right 指针访问两次，计算 gcd 和 lcm 的时间复杂度为 $O(n)$，但总体上时间复杂度得到了优化。

三、示例分析（以示例1为例）

• 输入 nums = [1,2,1,2,1,1,1]：
  • 从起始位置开始，逐步扩大窗口：
  • 当窗口为 [1] 时，prod = 1，gcd = 1，lcm = 1，满足条件，maxLen = 1。
  • 当窗口为 [1,2] 时，prod = 2，gcd = 1，lcm = 2，满足条件，maxLen = 2。
  • 当窗口为 [1,2,1] 时，prod = 2，gcd = 1，lcm = 2，满足条件，maxLen = 3。
  • 当窗口为 [1,2,1,2] 时，prod = 4，gcd = 1，lcm = 4，满足条件，maxLen = 4。
  • 当窗口为 [1,2,1,2,1] 时，prod = 4，gcd = 1，lcm = 4，满足条件，maxLen = 5。
  • 继续移动 right 指针，后续窗口都不满足条件，所以最终 maxLen = 5，输出 5。

综上所述，通过优化解法（滑动窗口）可以更高效地解决这道题，找到最长的“乘积等价子数组”的长度。

最大公约数（GCD）和最小公倍数（LCM）是两个数论中的重要概念，它们之间存在着密切的联系，具体如下：

一、基本定义

• 最大公约数：指两个或多个整数共有约数中最大的一个。例如，12 和 18 的公约数有 1、2、3、6，其中最大公约数是 6。
• 最小公倍数：指两个或多个整数公有的倍数中最小的一个。例如，12 和 18 的公倍数有 36、72、108 等，其中最小公倍数是 36。

二、两者联系

• 数学公式关系：对于两个正整数 $a$ 和 $b$，它们的乘积等于它们的最大公约数与最小公倍数的乘积，即 $a\times b=\text{GCD}(a,b)\times \text{LCM}(a,b)$。

例如，对于 4 和 6，$4\times 6=24$，4 和 6 的最大公约数是 2，最小公倍数是 12，$2\times 12=24$，满足上述公式。

三、实际应用中的体现

• 分数化简：在化简分数时，需要找到分子和分母的最大公约数，然后将分子分母同时除以最大公约数，得到最简分数。而最简分数的分母实际上就是原分子分母的最小公倍数的约数。例如，化简 $\frac{12}{18}$，先求出 12 和 18 的最大公约数是 6，化简后为 $\frac{2}{3}$，3 是 12 和 18 的最小公倍数 36 的约数。
• 周期性问题：在一些具有周期性的问题中，最大公约数和最小公倍数也有重要应用。比如，有两个周期性事件，一个周期为 $a$ 天，另一个周期为 $b$ 天，那么它们同时发生的周期就是 $a$ 和 $b$ 的最小公倍数，而在这个周期内，它们共同发生的次数与最大公约数有关。

总之，最大公约数和最小公倍数相互关联，在数论、代数、实际生活中的很多问题解决中都起着关键作用，帮助我们更好地理解和处理整数之间的关系和运算。

class Solution {
public:
    int maxLength(vector<int>& nums) {
        int n = nums.size();
        int ret = 0;
        for (int i = 0; i < n; i++) {
            unsigned long long prod = nums[i], l = nums[i], g = nums[i];
            if (prod == l * g) {
                ret = max(ret, 1);
            }
            for (int j = i + 1; j < n; j++) {
                prod *= nums[j];
                if (prod > ULONG_LONG_MAX) {
                    break;
                }
                l = (l * nums[j]) / gcd(l, nums[j]);
                g = gcd(g, nums[j]);
                if (prod == l * g) {
                    ret = max(ret, j - i + 1);
                }
            }
        }
        return ret;
    }
};