求数组排序后指定区间元素和的最优时间复杂度算法

Great question! Let's dig into how we can beat the O(n log n) sort-and-sum approach you mentioned with a linear-time average-case solution.

First, let's clarify the core of the problem: we don't need the entire array sorted—just the sum of elements that would sit between indices first and last (0-based, inclusive) in the sorted version. This lets us skip full sorting entirely and use a targeted, more efficient approach.

The Core Idea: Extended Quickselect #

We can adapt Quickselect—an algorithm that finds the k-th smallest element in average O(n) time—to not just locate elements, but calculate the sum of all elements in our target index range during the selection process. Here's how it works:

Step-by-Step Breakdown #

1. Pick a Random Pivot: Choosing a random pivot (instead of a fixed position) avoids the worst-case O(n²) behavior that can happen with adversarial inputs.
2. Partition the Array: Split the current subarray into three groups: elements smaller than the pivot, the pivot itself (since all elements are unique, this is a single element), and elements larger than the pivot.
3. Target Range Check:
   • If the entire target range lies within the smaller elements: Recurse on that subarray, keeping first and last unchanged.
   • If the entire target range lies within the larger elements: Recurse on that subarray, adjusting first and last by subtracting the length of the smaller + pivot groups.
   • If the target range spans all three groups:
     • Sum the relevant portion of the smaller elements (from first to the end of the smaller group, if applicable)
     • Add the pivot value
     • Sum the relevant portion of the larger elements (from the start of the larger group to the adjusted last, if applicable)
     • Return the total of these three parts

Example Walkthrough #

Using your sample input:

• first=3, last=7
• Array: {5,4,2,6,8,9,0,-1,3} (sorted becomes [-1,0,2,3,4,5,6,8,9], sum of indices 3-7 is 3+4+5+6+8=26)

1. Suppose we pick 5 as the pivot. Partition gives:
   • Smaller elements: [4,2,0,-1,3] (length 5)
   • Pivot: 5
   • Larger elements: [6,8,9] (length 3)
2. Our target range (3-7) spans all groups:
   • Sum the smaller group's elements from index 3 to 4 (sorted smaller group is [-1,0,2,3,4], sum is 3+4=7)
   • Add the pivot value: 5
   • Sum the larger group's elements from index 0 to 1 (sorted larger group is [6,8,9], sum is6+8=14)
   • Total sum: 7+5+14=26, which matches the sample output.

Simplified Pseudocode #

Here's a readable (non-space-optimized) version of the algorithm:

import random

def target_subarray_sum(arr, first, last):
    if first > last:
        return 0
    # Random pivot to avoid worst-case behavior
    pivot_idx = random.randint(0, len(arr)-1)
    pivot = arr[pivot_idx]
    
    # Partition array into three groups
    left = [x for x in arr if x < pivot]
    mid = [x for x in arr if x == pivot]  # Length 1 (unique elements)
    right = [x for x in arr if x > pivot]
    
    left_len = len(left)
    mid_len = len(mid)
    
    if last < left_len:
        # Target is entirely in the smaller elements
        return target_subarray_sum(left, first, last)
    elif first > left_len + mid_len - 1:
        # Target is entirely in the larger elements; adjust indices
        new_first = first - left_len - mid_len
        new_last = last - left_len - mid_len
        return target_subarray_sum(right, new_first, new_last)
    else:
        # Target spans all three groups
        sum_left = target_subarray_sum(left, first, left_len -1) if first <= left_len -1 else 0
        sum_right = target_subarray_sum(right, 0, last - left_len - mid_len) if last >= left_len + mid_len else 0
        return sum_left + sum(mid) + sum_right

Optimization Tips #

• In-Place Partitioning: The pseudocode creates new arrays for simplicity, but you can modify it to partition the array in-place (like standard Quickselect) to reduce space complexity from O(n) to O(log n) (due to the recursion stack).
• Strict Linear Worst-Case: If you need guaranteed O(n) time (not just average), use the Median of Medians method to select the pivot. It's more complex but eliminates the O(n²) worst case.

Complexity Comparison #

• Naive Sort-and-Sum: O(n log n) time, O(log n) space (for in-place sorting)
• Extended Quickselect: Average O(n) time, O(log n) space (with in-place partitioning); worst-case O(n²) time (effectively mitigated by random pivots)

For large arrays, the linear-time average case of this algorithm will outperform the sort-based approach by a significant margin.

内容的提问来源于stack exchange，提问作者Hubert Bratek