Python实现数组除自身以外元素的求和计算

Got it, let's break down how to solve this problem where we need to generate an output array where each element is the sum of all elements in the input nums array except the one at that index. Let's look at a few practical approaches in Python:

This is the most straightforward method—great for small arrays or when you just need a quick solution without worrying about performance. For each element, we iterate through the entire array and sum every element except the current one.

Time Complexity: O(n²) (nested loops mean we're doing n operations n times)
Space Complexity: O(n) (for the output array)

def sum_except_self_brute(nums):
    output = []
    for i in range(len(nums)):
        total = 0
        for j in range(len(nums)):
            if i != j:
                total += nums[j]
        output.append(total)
    return output

# Test with your example
nums = [6,7,8,9]
print(sum_except_self_brute(nums))  # Output: [24,23,22,21]

This method cuts down the time complexity to O(n) by precomputing two helper arrays:

• prefix[i]: Sum of all elements before index i
• suffix[i]: Sum of all elements after index i

Each element in the output is just the sum of prefix[i] and suffix[i].

Time Complexity: O(n) (three linear passes through the array)
Space Complexity: O(n) (for prefix, suffix, and output arrays)

def sum_except_self_prefix_suffix(nums):
    n = len(nums)
    prefix = [0] * n
    suffix = [0] * n
    output = [0] * n
    
    # Calculate prefix sums
    prefix[0] = 0
    for i in range(1, n):
        prefix[i] = prefix[i-1] + nums[i-1]
    
    # Calculate suffix sums
    suffix[-1] = 0
    for i in range(n-2, -1, -1):
        suffix[i] = suffix[i+1] + nums[i+1]
    
    # Build output array
    for i in range(n):
        output[i] = prefix[i] + suffix[i]
    
    return output

nums = [6,7,8,9]
print(sum_except_self_prefix_suffix(nums))  # Output: [24,23,22,21]

If we don't count the output array as "extra" space (since we need to return it anyway), we can optimize this to use O(1) additional space. We first populate the output array with prefix sums, then iterate backwards to add the suffix sums on the fly.

Time Complexity: O(n) (two linear passes)
Space Complexity: O(1) (only a single variable for suffix sum, plus the output array which is required)

def sum_except_self_optimized(nums):
    n = len(nums)
    output = [0] * n
    
    # First pass: fill output with prefix sums
    output[0] = 0
    for i in range(1, n):
        output[i] = output[i-1] + nums[i-1]
    
    # Second pass: add suffix sums to output
    suffix_sum = 0
    for i in range(n-1, -1, -1):
        output[i] += suffix_sum
        suffix_sum += nums[i]
    
    return output

nums = [6,7,8,9]
print(sum_except_self_optimized(nums))  # Output: [24,23,22,21]

Each approach has its use case—pick the brute force if you need simplicity, the prefix/suffix method for clarity, or the optimized version if you're working with large datasets and want to save space.

内容的提问来源于stack exchange，提问作者Blaze Lim