时间戳

首页 > 解决方案 > 如何优化在 3 个重复维度上使用“itertools.product”的代码？执行超时

python - 如何优化在 3 个重复维度上使用“itertools.product”的代码？执行超时

问题描述

此代码的目的是返回您可以将 seq 拆分为三个的次数，其中所有 3 个部分的整数之和相等。此代码适用于测试用例，但执行时超时。无论如何优化for循环，使其更快？

from itertools import product

def three_split(seq):
    answer=0
    q=0
    w=0
    e=0
    for i,j,k in product(range(1,len(seq)), repeat=3):
        if (i+j+k==len(seq)):
            q=sum(seq[:i])
            w=sum(seq[i:i+j])
            if q==w:
                e=sum(seq[i+j:])
                if w==e:
                    answer+=1
    
    return(answer)

标签： pythonoptimization

解决方案

您需要一个比O(N^3)更好的算法。首先，问题陈述简单地暗示每个子序列的总和必须通过target = sum(seq) / 3 计算这个目标总和开始。从这里开始，问题是“微不足道的”

  1. 找到每个前缀——每个位置i。sum(seq[:i]) == target这是O(N^2)，但运行总和会将其保持为O(N)。
  2. 同样，找到每个后缀——每个位置j。sum(seq[:j:]) == target这也是O(N^2)，可以保持为O(N)。
  3. 您的解决方案由 i<=j 的关于集合的所有对 (i, j) 组成。

代码：

target == sum(seq) // 3   # You might need to check that this sum is divisible by 3.
i_vals = [i for i in range(len(seq)) if sum(seq[:i]) == target]
j_vals = [j for j in range(len(seq)) if sum(seq[j:]) == target]

solution = [(i, j) for i in i_vals for j in j_vals if i <= j]

推荐阅读