1. 暴力求解
双重循环时间复杂度为 O(n2)
def subarrays_with_sum_equal_k(nums, k):
result = []
n = len(nums)
for start in range(n):
current_sum = 0
for end in range(start, n):
current_sum += nums[end]
if current_sum == k:
result.append(nums[start:end + 1])
return result
# 示例用法
nums = [10, 2, 2, 5, 4]
k = 4
result = subarrays_with_sum_equal_k(nums, k)
print("Subarrays with sum equal to {}:".format(k))
for subarray in result:
print(subarray)
截图如下所示：
如果是乘积，注意差异之处：
def subarrays_with_product_equal_k(nums, k):
result = []
n = len(nums)
for start in range(n):
prod = 1
for end in range(start, n):
prod *= nums[end]
if prod == k:
result.append(nums[start:end+1])
elif prod > k:
break
return result
# 示例用法
nums = [10, 2, 2, 5, 4]
k = 20
result = subarrays_with_product_equal_k(nums, k)
print("Subarrays with product equal to {}:".format(k))
for subarray in result:
print(subarray)
2. 前缀和哈希表
时间复杂度为O(n)
def subarrays_with_sum_equal_k(nums, k):
result = []
prefix_sum = 0 # 用于计算到当前元素的前缀和
prefix_sum_map = {0: [-1]} # 使用哈希表存储前缀和及其索引列表
for i, num in enumerate(nums):
prefix_sum += num
if (prefix_sum - k) in prefix_sum_map:
for start in prefix_sum_map[prefix_sum - k]:
result.append(nums[start + 1:i + 1])
if prefix_sum in prefix_sum_map:
prefix_sum_map[prefix_sum].append(i)
else:
prefix_sum_map[prefix_sum] = [i]
return result
# 示例用法
nums = [10, 2, -2, -20, 10]
k = -10
result = subarrays_with_sum_equal_k(nums, k)
print("Subarrays with sum equal to {}:".format(k))
for subarray in result:
print(subarray)
截图如下：
3. 滑动窗口
不适用于负数还有浮点小数的情况
def subarrays_with_sum_equal_k(nums, k):
result = []
current_sum = 0 # 存储当前窗口内元素的和
start = 0 # 滑动窗口的起始位置
for end in range(len(nums)):
current_sum += nums[end]
while current_sum > k and start <= end:
current_sum -= nums[start]
start += 1
if current_sum == k:
result.append(nums[start:end+1])
return result
# 示例用法
nums = [10, 2, 2, 5, 4]
k = 10
result = subarrays_with_sum_equal_k(nums, k)
print("Subarrays with sum equal to {}:".format(k))
for subarray in result:
print(subarray)
截图如下：
