Easy

题目描述

给定一个正整数数组 nums。

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

  • prod(arr) 是 arr 中所有元素的乘积。
  • gcd(arr) 是 arr 中所有元素的最大公约数。
  • lcm(arr) 是 arr 中所有元素的最小公倍数。

返回 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
  • 最大可能的 LCM 是多少？

解题思路

这道题需要理解乘积等价的数学含义。对于任意数组，有一个重要的数学性质：prod(arr) >= lcm(arr) * gcd(arr)，当且仅当数组中的所有数都相互整除或者满足特定的因子关系时等号成立。

核心思路：

  1. 暴力枚举所有子数组：由于数组长度最大为100，我们可以枚举所有可能的子数组。

  2. 数学分析：当 prod(arr) == lcm(arr) * gcd(arr) 时，这通常发生在以下情况：

    • 数组中只包含1和另一个数
    • 数组中的数具有特殊的因子关系
    • 单个元素的数组

  3. 优化观察：由于 nums[i] <= 10，我们可以分析哪些数字组合可能满足乘积等价条件。通过数学推导，主要的情况包括：

    • 包含多个1的数组
    • 某些特定数字的组合

  4. 实现策略：

    • 枚举所有子数组的起始和结束位置
    • 对每个子数组计算 GCD、LCM 和乘积
    • 检查是否满足乘积等价条件
    • 记录满足条件的最长子数组长度

时间复杂度优化：虽然是三重循环，但由于数组长度限制在100以内，总体复杂度是可接受的。

代码实现

class Solution {
public:
    int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
    
    long long lcm(long long a, long long b) {
        return a * b / gcd(a, b);
    }
    
    int maxLength(vector<int>& nums) {
        int n = nums.size();
        int maxLen = 1;
        
        for (int i = 0; i < n; i++) {
            long long prod = 1;
            int g = nums[i];
            long long l = nums[i];
            
            for (int j = i; j < n; j++) {
                prod *= nums[j];
                g = gcd(g, nums[j]);
                l = lcm(l, nums[j]);
                
                if (prod == l * g) {
                    maxLen = max(maxLen, j - i + 1);
                }
                
                // 避免溢出
                if (prod > 1e18) break;
            }
        }
        
        return maxLen;
    }
};

class Solution:
    def maxLength(self, nums: List[int]) -> int:
        import math
        
        def lcm(a, b):
            return a * b // math.gcd(a, b)
        
        n = len(nums)
        max_len = 1
        
        for i in range(n):
            prod = 1
            g = nums[i]
            l = nums[i]
            
            for j in range(i, n):
                prod *= nums[j]
                g = math.gcd(g, nums[j])
                l = lcm(l, nums[j])
                
                if prod == l * g:
                    max_len = max(max_len, j - i + 1)
                
                # 避免溢出
                if prod > 10**18:
                    break
        
        return max_len

public class Solution {
    private int Gcd(int a, int b) {
        return b == 0 ? a : Gcd(b, a % b);
    }
    
    private long Lcm(long a, long b) {
        return a * b / Gcd((int)a, (int)b);
    }
    
    public int MaxLength(int[] nums) {
        int n = nums.Length;
        int maxLen = 1;
        
        for (int i = 0; i < n; i++) {
            long prod = 1;
            int g = nums[i];
            long l = nums[i];
            
            for (int j = i; j < n; j++) {
                prod *= nums[j];
                g = Gcd(g, nums[j]);
                l = Lcm(l, nums[j]);
                
                if (prod == l * g) {
                    maxLen = Math.Max(maxLen, j - i + 1);
                }
                
                // 避免溢出
                if (prod > 1000000000000000000L) break;
            }
        }
        
        return maxLen;
    }
}

var maxLength = function(nums) {
    function gcd(a, b) {
        return b === 0 ? a : gcd(b, a % b);
    }
    
    function lcm(a, b) {
        return (a * b) / gcd(a, b);
    }
    
    function arrayGcd(arr) {
        return arr.reduce((acc, val) => gcd(acc, val));
    }
    
    function arrayLcm(arr) {
        return arr.reduce((acc, val) => lcm(acc, val));
    }
    
    function arrayProduct(arr) {
        return arr.reduce((acc, val) => acc * val, 1);
    }
    
    function isProductEquivalent(arr) {
        const prod = arrayProduct(arr);
        const g = arrayGcd(arr);
        const l = arrayLcm(arr);
        return prod === l * g;
    }
    
    let maxLen = 0;
    
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            const subarray = nums.slice(i, j + 1);
            if (isProductEquivalent(subarray)) {
                maxLen = Math.max(maxLen, subarray.length);
            }
        }
    }
    
    return maxLen;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n²)枚举所有子数组，每次计算GCD和LCM的时间复杂度为O(log(max(nums)))
空间复杂度O(1)只使用常数额外空间

相关题目