给你一个由 正整数 组成的数组 nums。

如果一个数组 arr 满足 prod(arr) == lcm(arr) * gcd(arr)，则称其为 乘积等价数组 ，其中：

  • prod(arr) 表示 arr 中所有元素的乘积。

  • gcd(arr) 表示 arr 中所有元素的最大公因数 (GCD)。

  • lcm(arr) 表示 arr 中所有元素的最小公倍数 (LCM)。

返回数组 nums 的 最长 乘积等价 子数组 的长度。

示例 1：

输入： nums = [1,2,1,2,1,1,1]

输出： 5

解释： 

最长的乘积等价子数组是 [1, 2, 1, 1, 1]，其中 prod([1, 2, 1, 1, 1]) = 2， gcd([1, 2, 1, 1, 1]) = 1，以及 lcm([1, 2, 1, 1, 1]) = 2。

示例 2：

输入： nums = [2,3,4,5,6]

输出： 3

解释： 

最长的乘积等价子数组是 [3, 4, 5]。

示例 3：

输入： nums = [1,2,3,1,4,5,1]

输出： 5

提示：

  • 2 <= nums.length <= 100

  • 1 <= nums[i] <= 10

思路

  • 滑动窗口+范围[1,10]+每种质数个数不超过1(玄学)

代码

  • 滑动窗口+范围[1,10]+每种质数个数不超过1

class Solution {
    public int maxLength(int[] nums) {
        int result = 2; // 保持原有初始值（假设最小有效长度为2）
        int two = 0;    // 统计当前窗口内能被2整除的数字个数
        int three = 0;  // 统计能被3整除的数字个数
        int five = 0;   // 统计能被5整除的数字个数
        int seven = 0;  // 统计能被7整除的数字个数
        int left = 0;   // 滑动窗口左指针（原名index，改为left更表意）
        
        for (int right = 0; right < nums.length; right++) {
            // 更新当前数字的整除统计
            if ((nums[right] & 1) == 0) two++;
            if (nums[right] % 3 == 0) three++;
            if (nums[right] % 5 == 0) five++;
            if (nums[right] % 7 == 0) seven++;
            
            // 当任一统计值超过1时，收缩窗口左边界
            while (two > 1 || three > 1 || five > 1 || seven > 1) {
                if ((nums[left] & 1) == 0) two--;
                if (nums[left] % 3 == 0) three--;
                if (nums[left] % 5 == 0) five--;
                if (nums[left] % 7 == 0) seven--;
                left++;
            }
            
            // 更新最大窗口长度
            result = Math.max(result, right - left + 1);
        }
        return result;
    }
}