如何用JavaScript以O(nlog(n))时间复杂度获取所有子数组

先明确一点：如果是要枚举所有子数组的元素本身，那不管用什么方法，时间复杂度都是O(n²)——毕竟子数组总数就是n(n+1)/2个，没法绕开。但如果是处理子数组的衍生问题（比如求和、统计满足条件的子数组数量），前缀和能帮你优化计算效率，甚至把时间复杂度降到O(n)。

1. 前缀和数组的基本构建 #

前缀和数组prefix的核心逻辑是：prefix[i]代表原数组前i个元素的累加和（通常让prefix[0] = 0，对应“前0个元素和为0”的边界情况）。

举个Python实现的例子：

nums = [1, 2, 3, 4]
prefix = [0] * (len(nums) + 1)
for i in range(len(nums)):
    prefix[i+1] = prefix[i] + nums[i]

最终prefix数组是[0, 1, 3, 6, 10]，对应原数组前0个、前1个、前2个...前4个元素的和。有了这个数组，任意子数组nums[j..i-1]（从索引j到i-1的元素）的和，都可以用prefix[i] - prefix[j]直接算出，不用再循环累加。

2. 替代嵌套循环计算所有子数组的和 #

如果你的需求是计算所有子数组的和，原来的嵌套循环是内层逐个累加，用前缀和可以把求和操作变成O(1)的减法：

原嵌套循环实现（O(n²)时间） #

nums = [1,2,3,4]
subarray_sums = []
for i in range(len(nums)):
    current_sum = 0
    for j in range(i, len(nums)):
        current_sum += nums[j]
        subarray_sums.append(current_sum)

前缀和实现（同样O(n²)时间，但计算更高效） #

nums = [1,2,3,4]
prefix = [0]*(len(nums)+1)
for i in range(len(nums)):
    prefix[i+1] = prefix[i] + nums[i]

subarray_sums = []
# 遍历所有可能的子数组结束位置（对应prefix的i）
for i in range(1, len(prefix)):
    # 遍历所有可能的子数组起始位置（对应prefix的j）
    for j in range(i):
        subarray_sums.append(prefix[i] - prefix[j])

这种写法避免了内层循环的重复累加，数据量越大，性能提升越明显。

3. 用前缀和+哈希表优化统计类问题（O(n)时间） #

如果是统计和为目标值k的子数组数量这类问题，前缀和结合哈希表可以把时间复杂度降到O(n)，这才是前缀和真正的优势所在：

def count_subarrays_with_sum_k(nums, k):
    # 哈希表记录前缀和出现的次数，初始时前缀和0出现1次（处理从数组开头的子数组）
    prefix_count = {0: 1}
    current_prefix = 0
    count = 0
    
    for num in nums:
        current_prefix += num
        # 如果current_prefix - k存在，说明存在j使得prefix[i]-prefix[j]=k，即子数组j..i-1的和为k
        if current_prefix - k in prefix_count:
            count += prefix_count[current_prefix - k]
        # 更新当前前缀和的出现次数
        prefix_count[current_prefix] = prefix_count.get(current_prefix, 0) + 1
    
    return count

这个方法通过哈希表记录已经出现过的前缀和，每一步都能直接算出符合条件的子数组数量，完全不需要嵌套循环。

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