Python中如何避免多层嵌套for循环（含迭代范围依赖外层场景）

首先，我们来拆解你的问题：你需要找出数组中满足 arr[i] - arr[j] = arr[j] - arr[k] = d 且 i < j < k 的三元组。原代码用了三层嵌套循环，时间复杂度是O(n³)，当数组规模变大时效率会极低。下面我会给出几种优化方案，帮你摆脱多层嵌套的困扰。

核心思路：把循环验证转化为查找问题 #

原问题的条件可以等价转换：对于中间元素 arr[j]，我们需要找到arr[j] - d（对应arr[k]，且k < j）和arr[j] + d（对应arr[i]，且i > j）——哦不对，等一下，根据你给出的条件arr[i]-arr[j] = d和arr[j]-arr[k] = d，应该是arr[i] = arr[j] + d，arr[k] = arr[j] - d，同时i < j < k？这在递增数组里其实不成立（因为k > j的话arr[k]应该比arr[j]大），所以我推测你可能是想找公差为d的等差数列三元组，也就是arr[j] - arr[i] = arr[k] - arr[j] = d且i < j < k。下面的方案我会基于这个更常见的场景来写，如果你的需求确实是原条件，只需要调整查找的目标值即可。

方案一：用哈希表快速定位元素和索引 #

我们可以先把数组元素和对应的索引存到字典里，然后遍历每个可能的中间索引j，直接查找是否存在符合条件的左右元素，同时验证索引顺序：

from collections import defaultdict

arr = [1, 2, 4, 5, 7, 8, 10]
d = 3
list1 = []

# 构建元素到所有索引的映射（处理重复元素）
element_indices = defaultdict(list)
for idx, num in enumerate(arr):
    element_indices[num].append(idx)

# 遍历每个中间元素的索引j
for j in range(len(arr)):
    left_val = arr[j] - d  # 左边需要的元素值（arr[i]）
    right_val = arr[j] + d  # 右边需要的元素值（arr[k]）
    
    # 检查左边是否存在符合条件的i（i < j）
    if left_val in element_indices:
        for i in element_indices[left_val]:
            if i < j:
                # 检查右边是否存在符合条件的k（k > j）
                if right_val in element_indices:
                    for k in element_indices[right_val]:
                        if k > j:
                            list1.append((arr[i], arr[j], arr[k]))

print(list1)  # 输出: [(1, 4, 7), (2, 5, 8), (4, 7, 10)]

这个方案的时间复杂度平均情况下是O(n²)（最坏情况如果有大量重复元素可能接近O(n³)，但远好于原生三层循环），因为我们用哈希表把内层的遍历查找变成了快速定位。

方案二：有序数组用二分查找优化 #

如果你的数组是有序的（比如示例中的数组），可以用二分查找进一步降低查找的时间复杂度：

import bisect

arr = [1, 2, 4, 5, 7, 8, 10]
d = 3
list1 = []

n = len(arr)
for j in range(n):
    left_val = arr[j] - d
    # 二分查找左边元素的位置
    left_pos = bisect.bisect_left(arr, left_val)
    if left_pos < j and arr[left_pos] == left_val:
        # 找到所有符合i < j的索引
        left_start = bisect.bisect_left(arr, left_val)
        left_end = bisect.bisect_right(arr, left_val)
        right_val = arr[j] + d
        # 二分查找右边元素的位置
        right_pos = bisect.bisect_right(arr, right_val) - 1
        if right_pos > j and arr[right_pos] == right_val:
            # 找到所有符合k > j的索引
            right_start = bisect.bisect_left(arr, right_val)
            right_end = bisect.bisect_right(arr, right_val)
            # 收集所有符合条件的三元组
            for i in range(left_start, left_end):
                if i < j:
                    for k in range(right_start, right_end):
                        if k > j:
                            list1.append((arr[i], arr[j], arr[k]))

print(list1)

这个方案的时间复杂度是O(n log n)（排序如果数组无序的话）加上O(n log n)的遍历和二分查找，整体效率比哈希表方案更稳定，尤其适合大规模有序数组。

方案三：直接遍历+哈希表查找（简化版） #

如果只需要收集元素值而非索引，还可以更简化：遍历每个元素作为等差数列的第一个元素，然后直接查找后两个元素是否存在：

from collections import defaultdict

arr = [1, 2, 4, 5, 7, 8, 10]
d = 3
list1 = []
element_set = set(arr)
# 存储元素到索引的映射，用于验证顺序
element_indices = {num: idx for idx, num in enumerate(arr)}

for num in arr:
    mid_num = num + d
    end_num = mid_num + d
    if mid_num in element_set and end_num in element_set:
        # 验证索引顺序：num的索引 < mid_num的索引 < end_num的索引
        if element_indices[num] < element_indices[mid_num] < element_indices[end_num]:
            list1.append((num, mid_num, end_num))

print(list1)

这个方案更简洁，时间复杂度是O(n)，但只适用于数组中元素不重复的情况（如果有重复元素，需要调整映射为索引列表）。

通用优化思路总结 #

当遇到多层嵌套循环且内层循环依赖外层迭代值时，你可以：

• 重构问题条件：把循环需要验证的条件转化为“查找是否存在满足要求的元素”，减少嵌套层数；
• 使用哈希表/集合：提前存储元素信息，将O(n)的遍历查找转化为O(1)的快速查找；
• 利用有序特性：如果数组有序，用二分查找、双指针等方法进一步降低时间复杂度；
• 减少不必要的遍历：只遍历可能符合条件的元素范围，而非整个数组。

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