寻找和等于k的子数组问题《计算之魂》

sum_k_problem.py

# 寻找和等于k的子数组问题《计算之魂》
data = [5, 2, 7, 0, 0, 8, 7, 1, 1, 2, 5, 6]
k = 9

# 部分和字典
part_sum_dict = {}
result_number = 0
current_sum = 0

for i, num in enumerate(data):
    current_sum += num

    if current_sum == k:
        result_number += 1

    if current_sum in part_sum_dict:
        count = part_sum_dict[current_sum][0]
        part_sum_dict[current_sum] = (count + 1, current_sum - k)
    else:
        part_sum_dict[current_sum] = (1, current_sum - k)

    if current_sum - k in part_sum_dict:
        result_number += 1

print(result_number)  # 5
print(part_sum_dict)
# {5: (1, -4), 7: (1, -2), 14: (3, 5), 22: (1, 13), 29: (1, 20), 30: (1, 21),
# 31: (1, 22), 33: (1, 24), 38: (1, 29), 44: (1, 35)}