如何查找数组中所有包含指定值的连续索引元素组合？

给定元素无重复、长度可变的数组，需要查找所有满足以下两个条件的元素组合：

• 组合内元素在原数组中的索引是连续相邻的
• 组合必须包含指定的目标值
  注：组合内部元素顺序无强制要求，示例中保留原数组顺序仅为便于演示

给定测试数组[5, 4, 2, 0, 1, 3]

当目标值为0时，共得到12种符合要求的组合 #

• [0]
• [0, 1]
• [2, 0]
• [0, 1, 3]
• [2, 0, 1]
• [4, 2, 0]
• [2, 0, 1, 3]
• [4, 2, 0, 1]
• [5, 4, 2, 0]
• [4, 2, 0, 1, 3]
• [5, 4, 2, 0, 1]
• [5, 4, 2, 0, 1, 3]

当目标值为3时，共得到6种符合要求的组合 #

• [3]
• [1, 3]
• [0, 1, 3]
• [2, 0, 1, 3]
• [4, 2, 0, 1, 3]
• [5, 4, 2, 0, 1, 3]

基础兜底方案 #

可先枚举原数组的所有连续索引子序列，再筛选出包含目标值的子序列输出即可。该方案并非效率最优，但实现门槛极低，任意编程语言都可快速落地。

高效优化思路 #

不需要全量枚举所有子序列，只要先定位目标值在数组中的索引位置，所有符合要求的连续子序列必然满足：左边界在目标值左侧（含目标值本身位置）、右边界在目标值右侧（含目标值本身位置）。
结果校验：

• 假设目标值索引为target_idx，数组总长度为n
• 左边界的可选范围为0 ~ target_idx，共 target_idx + 1 种选择
• 右边界的可选范围为target_idx ~ n-1，共 n - target_idx 种选择
• 最终符合要求的组合总数为两者的乘积，和示例计算结果完全匹配：目标值0的索引为3，左边界有4种选择、右边界有3种选择，乘积12和示例结果一致；目标值3的索引为5，左边界有6种选择、右边界有1种选择，乘积6和示例结果一致。
  该逻辑不绑定特定编程语言，可根据技术栈自由实现。

Python实现示例 #

def get_valid_combinations(arr: list, target):
    # 定位目标值的索引位置
    target_pos = arr.index(target)
    arr_len = len(arr)
    result = []
    # 枚举所有合法左边界
    for left in range(target_pos + 1):
        # 枚举所有合法右边界
        for right in range(target_pos, arr_len):
            result.append(arr[left:right+1])
    return result

# 测试用例
test_array = [5, 4, 2, 0, 1, 3]
# 输出目标值为0的所有组合
print(get_valid_combinations(test_array, 0))
# 输出目标值为3的所有组合
print(get_valid_combinations(test_array, 3))

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