python-3.x 查找数组中最短的子数组,该子数组在给定数组中的索引之和等于该子数组的元素之和

fcg9iug3  于 2022-12-15  发布在  Python
关注(0)|答案(1)|浏览(140)

我几乎是一个初学者程序员,想要学习如何编写算法。我刚刚写了一个程序,寻找最短子数组数组中的(子集),其在给定数组中的索引之和等于子数组元素之和(子集)并打印出总和。问题是,我需要跟踪子数组中的数字数量(以找到最短的一个)以及所选元素的总和(因为我想保存它或者只是打印它),所以我想递归地返回一个2元素的数组,但是无论我用什么方法尝试,最后我遇到了一个错误,比如“NoneType不可订阅”或者在'NoneType'和'NoneType'的示例之间不支持'〈',所以我使用了一个全局变量并以这种方式解决了这个问题。但是我如何避免在这类问题中使用全局变量呢?下面是我的代码,请教我如何在没有全局变量的情况下解决这类问题:

best_sum = math.inf

def SumIndexesEqualSumElements(T, idx=0, idxsum=0, tabsum=0, count=0):
    global best_sum
    if idx==len(T):
        if count==0:
            return math.inf
        if idxsum==tabsum:
            best_sum = tabsum
            return count
        return math.inf
    return min(SumIndexesEqualSumElements(T,idx+1,idxsum+idx,tabsum+T[idx],count+1),
               SumIndexesEqualSumElements(T,idx+1,idxsum,tabsum,count))

SumIndexesEqualSumElements([1,7,3,5,11,2])
print(best_sum)
u1ehiz5o

u1ehiz5o1#

您的代码正在查找索引和相等的数组的子集
我建议你解决初级水平-子数组子集问题。然后,来这个。
对于这道题,你可以用暴力破解数组,找出所有子数组的和和索引和。然后,选择最好的一个--最短的(这里)

def SumIndexesEqualSumElements(arr):
    best_length = len(arr)
    ans_sum = 0
    for i in range(len(arr)):
        indices_sum = 0
        elements_sum = 0
        length = 0
        for j in range(i,len(arr)):
            indices_sum += j
            elements_sum += arr[j]
            length += 1
            if indices_sum == elements_sum:
                if length < best_length:
                    best_length = length
                    ans_sum = elements_sum
    return ans_sum
print(SumIndexesEqualSumElements([1,3,3,0,11,2]))

使用基于0的索引

相关问题