LeetCode 题解工作台
分割数组使乘积互质
给你一个长度为 n 的整数数组 nums ，下标从 0 开始。 如果在下标 i 处 分割 数组，其中 0 ，使前 i + 1 个元素的乘积和剩余元素的乘积互质，则认为该分割 有效 。 例如，如果 nums = [2, 3, 3] ，那么在下标 i = 0 处的分割有效，因为 2 和 9 互质，而在下…
4
题型
4
代码语言
3
相关题
当前训练重点
困难 · 数组·哈希·扫描
答案摘要
class Solution: def findValidSplit(self, nums: List[int]) -> int:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个长度为 n 的整数数组 nums ，下标从 0 开始。
如果在下标 i 处 分割 数组，其中 0 <= i <= n - 2 ，使前 i + 1 个元素的乘积和剩余元素的乘积互质，则认为该分割 有效 。
- 例如，如果
nums = [2, 3, 3]，那么在下标i = 0处的分割有效，因为2和9互质，而在下标i = 1处的分割无效，因为6和3不互质。在下标i = 2处的分割也无效，因为i == n - 1。
返回可以有效分割数组的最小下标 i ，如果不存在有效分割，则返回 -1 。
当且仅当 gcd(val1, val2) == 1 成立时，val1 和 val2 这两个值才是互质的，其中 gcd(val1, val2) 表示 val1 和 val2 的最大公约数。
示例 1：
输入：nums = [4,7,8,15,3,5] 输出：2 解释：上表展示了每个下标 i 处的前 i + 1 个元素的乘积、剩余元素的乘积和它们的最大公约数的值。 唯一一个有效分割位于下标 2 。
示例 2：
输入：nums = [4,7,15,8,3,5] 输出：-1 解释：上表展示了每个下标 i 处的前 i + 1 个元素的乘积、剩余元素的乘积和它们的最大公约数的值。 不存在有效分割。
提示：
n == nums.length1 <= n <= 1041 <= nums[i] <= 106
解题思路
方法一：质因数分解
class Solution:
def findValidSplit(self, nums: List[int]) -> int:
first = {}
n = len(nums)
last = list(range(n))
for i, x in enumerate(nums):
j = 2
while j <= x // j:
if x % j == 0:
if j in first:
last[first[j]] = i
else:
first[j] = i
while x % j == 0:
x //= j
j += 1
if x > 1:
if x in first:
last[first[x]] = i
else:
first[x] = i
mx = last[0]
for i, x in enumerate(last):
if mx < i:
return mx
mx = max(mx, x)
return -1
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on prime factorization per element and array scanning, roughly O(n log(max(nums[i]))). Space complexity is dominated by the hash map storing prime counts, up to O(n log(max(nums[i]))) primes in worst case. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Check if your solution avoids computing large products directly.
- question_mark
Ensure your prime factor tracking correctly identifies overlapping primes between subarrays.
- question_mark
Consider early stopping once the first valid split is detected.
常见陷阱
外企场景- error
Attempting to multiply all elements causes integer overflow.
- error
Forgetting to account for multiple occurrences of the same prime factor across the array.
- error
Returning an index too late instead of the minimal valid index.
进阶变体
外企场景- arrow_right_alt
Find all valid split indices instead of just the smallest one.
- arrow_right_alt
Return the maximum index where a coprime split is possible.
- arrow_right_alt
Allow elements to be negative, adjusting GCD calculations accordingly.