代码之家 › 专栏 › 技术社区 › mchd

查找数组的连续和

algorithm python

mchd · 技术社区 · 6 年前

我正在应对一个编码挑战。这个挑战基本上是想让我找到它的k个连续元素的最大和。以下是一个示例:

For inputArray = [2, 3, 5, 1, 6] 和 k = 2 ,输出应为 arrayMaxConsecutiveSum(inputArray, k) = 8 . 2个连续元素的所有可能总和为:

2 + 3 = 5;
3 + 5 = 8;
5 + 1 = 6;
1 + 6 = 7.

因此,答案是8。

这是我的尝试。我将连续的总和视为子列表。如果我有 k=3 ,那么我必须在I后面添加2个元素。因此,如果开始是索引0,那么结束是开始+k-1。然后,我尝试使用for循环将每k个块的总和附加到一个新列表中。我的最终目标是归还 max() 从这个列表中:

def arrayMaxConsecutiveSum(inputArray, k):
    begin = 0
    end = begin + (k-1)
    sum_list = []
    
    for i in range(0, len(inputArray)):
        begin = i
        sum_list.append(sum(inputArray[begin:end+1]))
    
    print(sum_list)

现在我只想看看我的 sum_list 看起来就像我试图返回它的最大值之前一样。但是,这是它在测试用例中返回的结果:

Input: inputArray: [2, 3, 5, 1, 6]
k: 2
Output: null
Expected Output: 8
Console Output: [5, 3, 0, 0, 0]

我认为我的逻辑是正确的。我只想知道我在哪里犯了错误。

5 回复 | 直到 6 年前

Iain Shelvington 6 年前

一个相当有效的解决方案是使用 itertools.islice 和 zip 用于生成连续元素组。这消除了对列表进行切片的需要

consecutive_elements = zip(*(islice(inputArray, x, None) for x in range(k)))

islice生成器生成的示例:

>>> [list(islice(range(5), x, None)) for x in range(3)]
[[0, 1, 2, 3, 4], [1, 2, 3, 4], [2, 3, 4]]

islice(inputArray, x, None) for x in range(k) 从输入中创建可迭代对象,分割出越来越多的元素,并将其传递给 拉链 然后加入iterables元素,创建组

然后使用 map 生成总和,而不是创建中间列表

return max(map(sum, consecutive_elements))

Ali Hassan 6 年前

你需要更新你的结束索引。

def arrayMaxConsecutiveSum(inputArray, k):
    begin = 0
    end = begin + k
    sum_list = []

    for i in range(0, len(inputArray)):
    
        sum_list.append(sum(inputArray[i:i + k]))

    print(sum_list)

Akshay Sehgal 6 年前

如果你想在不使用任何其他库的情况下获得更易读的内容,例如 itertools ,你可以试试这个内衬-

[sum(i) for i in zip(*(inputArray[i:] for i in range(k)))]

[5, 8, 6, 7]

调试代码:

代码中有一些错误。首先,定义循环外的结束。在开始更改时,您也希望循环中的结束更改。此外,由于python已经考虑了 n-1 结束索引,您只需将其设置为 begin+k 而不是 begin+(k-1) 接下来,您需要将迭代器从0移动到length或array-1,因为最后一个项将只是一个元素。如果你想看看哪里出了问题,我已经修改了代码,使其按照你的期望运行-

def arrayMaxConsecutiveSum(inputArray, k):
    #begin = 0 #<--- #No need since you are setting it to i in loop
    #end = begin + k #<--- Not to be defined here but inside loop
    sum_list = []
    
    for i in range(0, len(inputArray)-1): #<----
        begin = i
        end = begin + k #<--- 
        sum_list.append(sum(inputArray[begin:end])) #<----
    
    print(sum_list)

[5, 8, 6, 7]

Deepak Tripathi 6 年前

在这种情况下,取给定索引到索引+k的总和(5-(k-1))次,然后取最大值

inputArray = [2, 3, 5, 1, 6]
k = 3
print(max([sum(inputArray[idx : idx + k]) for idx in range(len(inputArray)-(k-1))]))