如何在Python列表中查找和为90的子列表？

嘿，这个问题得先明确你要找的是连续的子数组还是非连续的子序列——毕竟你给出的两个例子里，[50,40]在原数组里是不连续的，而[30,50,10]（我猜你可能笔误写成了[50,30,10]）是连续的。下面我给你两种场景的实现方案：

因为你的数组里全是正数，用滑动窗口法效率最高，时间复杂度是O(n)，比暴力枚举的O(n²)快很多。思路就是用两个指针维护一个窗口，动态调整窗口内元素的和，直到找到等于目标值的窗口。

def find_continuous_subarray(arr, target):
    left = 0
    current_sum = 0
    
    for right in range(len(arr)):
        current_sum += arr[right]
        
        # 当窗口内的和超过目标值时，移动左指针缩小窗口
        while current_sum > target and left <= right:
            current_sum -= arr[left]
            left += 1
        
        # 找到符合条件的连续子数组，直接返回
        if current_sum == target:
            return arr[left:right+1]
    
    # 如果遍历完都没找到，返回空列表
    return []

# 测试代码
original_arr = [100, 150, 30, 50, 10, 20, 40]
target_sum = 90
print(find_continuous_subarray(original_arr, target_sum))  # 输出: [30, 50, 10]

如果要找像[50,40]这种不连续的子序列，可以用回溯法来枚举所有可能的元素组合，筛选出和为90的结果。这种方法会找出所有符合条件的子序列，如果你只需要其中一个，可以在找到后立刻终止递归。

def find_subsequences(arr, target):
    result = []
    
    def backtrack(start_index, current_path, current_sum):
        # 找到符合条件的子序列，加入结果列表
        if current_sum == target:
            result.append(current_path.copy())
            return
        # 如果当前和超过目标值，或者遍历完所有元素，直接返回
        if current_sum > target or start_index >= len(arr):
            return
        
        # 选择当前元素，继续递归
        current_path.append(arr[start_index])
        backtrack(start_index + 1, current_path, current_sum + arr[start_index])
        
        # 不选择当前元素，继续递归（回溯）
        current_path.pop()
        backtrack(start_index + 1, current_path, current_sum)
    
    backtrack(0, [], 0)
    return result

# 测试代码
original_arr = [100, 150, 30, 50, 10, 20, 40]
target_sum = 90
print(find_subsequences(original_arr, target_sum))
# 输出会包含所有符合条件的子序列：[[30, 50, 10], [30, 20, 40], [50, 40]]

如果只需要第一个找到的非连续子序列，可以修改回溯函数，找到后立刻返回：

def find_one_subsequence(arr, target):
    def backtrack(start_index, current_path, current_sum):
        if current_sum == target:
            return current_path.copy()
        if current_sum > target or start_index >= len(arr):
            return None
        
        # 选择当前元素
        res = backtrack(start_index + 1, current_path + [arr[start_index]], current_sum + arr[start_index])
        if res is not None:
            return res
        
        # 不选择当前元素
        return backtrack(start_index + 1, current_path, current_sum)
    
    return backtrack(0, [], 0)

print(find_one_subsequence(original_arr, target_sum))  # 输出第一个找到的子序列，比如[30,50,10]

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