如何用嵌套循环高效实现序列元素逐对求和至单个结果？

Hey there! Let's break down how to solve this problem—both with clear iterative logic and optimized approaches for large datasets.

Understanding the Process #

First, let's recap what we're aiming for with your example list [1,2,3,4,5]:

1. First pair sums: [1+2, 2+3, 3+4,4+5] → [3,5,7,9]
2. Second pair sums: [3+5,5+7,7+9] → [8,12,16]
3. Third pair sums: [8+12,12+16] → [20,28]
4. Final sum: 20+28 → 48

Basic Iterative Approach (Easy to Read) #

If you're just getting the hang of the loop logic, this straightforward method will work. We keep generating new lists of pair sums until only one value remains:

the_list = [1, 2, 3, 4, 5]
current = the_list.copy()  # Preserve the original list

while len(current) > 1:
    # Generate next list by summing adjacent elements
    current = [current[i] + current[i+1] for i in range(len(current)-1)]

print(current[0])  # Output: 48

This is simple to understand, but as you noted, creating a new list each iteration can be inefficient for very large datasets (it uses extra memory and has O(n²) time complexity).

Memory-Optimized In-Place Modification #

Instead of creating new lists every time, we can modify the existing list in place. This cuts down on memory overhead since we're reusing the same list structure:

the_list = [1, 2, 3, 4, 5]
current = the_list.copy()

while len(current) > 1:
    # Update elements in place by summing adjacent pairs
    for i in range(len(current)-1):
        current[i] = current[i] + current[i+1]
    # Remove the last element (it's no longer needed after merging)
    current.pop()

print(current[0])  # Output: 48

This approach still has O(n²) time complexity, but it uses significantly less memory for large lists.

Optimal Mathematical Approach (O(n) Time) #

Here's a pro tip: this repeated pair-summing process is mathematically equivalent to calculating the sum of each original element multiplied by a binomial coefficient (from Pascal's Triangle). For a list of length n, the i-th element (0-indexed) gets multiplied by C(n-1, i) (the combination of n-1 choose i).

For your example with n=5, the coefficients are C(4,0)=1, C(4,1)=4, C(4,2)=6, C(4,3)=4, C(4,4)=1. Calculating the total:
(1*1) + (2*4) + (3*6) + (4*4) + (5*1) = 1 + 8 + 18 + 16 +5 =48

Implementing this with Python's built-in math.comb (available in Python 3.10+):

import math

the_list = [1, 2, 3, 4, 5]
n = len(the_list)
total = 0

for idx, num in enumerate(the_list):
    total += num * math.comb(n-1, idx)

print(total)  # Output:48

This method runs in O(n) time and uses minimal memory—perfect for large datasets where performance matters.

内容的提问来源于stack exchange，提问作者Tomasz Przemski