时间戳

首页 > 解决方案 > 在 3 个相等和的列表中找到 2 个索引用于列表细分的可能性

python - 在 3 个相等和的列表中找到 2 个索引用于列表细分的可能性

问题描述

我必须编写一个函数，该函数将整数列表（ls）作为输入并根据条件返回 True 或 False：

  1. 如果存在任何 2 个索引 (ix1,ix2)，则忽略列表中的那些元素并分解为 3 个较小的列表，这样如果sum(ls[0:ix1])==sum(ls[(ix1+1):ix2])==sum(ls[ix2+1:])返回 True

例如if list=[1, 3, 4, 2, 2, 2, 1, 1, 2],它应该返回True,，因为对于索引 2,5-> 1+3==2+2==1+1+2

我尝试编写以下函数，但似乎效率不高：

def func(A):
    y=False
    for i in range(len(A)-2):
        for j in range(len(A)-i-3):
          t1=A[0:i]
          t2=A[(i+1):j+i+2]
          t3=A[j+i+3:]
          if sum(t1)==sum(t2)==sum(t3):
              y=True
              break
        if y==True:break

    return y

但我想不出搜索索引 ix1、ix2 的最佳方法，除了尝试所有索引组合

标签： pythonalgorithmlistperformanceload-balancing

解决方案

我可以为更好的算法提供优化和方法。

您应该首先创建一个 sum_list ，其中每个元素将等于所有先前元素的总和，因此对于问题中的示例， sum_list 将是sum_list = [1,4,7,9,11,13,14,15,17]。

现在，您不必每次都计算总和，而只需取 sum_list 中某些元素的差值即可找到总和，使其成为 O(1) 运算。

更好的算法是在 sum_list 数组上使用两个指针。它们将在开始时初始化为一个，在结束时初始化为一个。然后你计算所有的总和，如果一个总和小于或大于另一个总和，你可以移动指针。

推荐阅读