方法一：dp+前缀和 O(N)
class Solution: def minSumOfLengths(self, arr: List[int], target: int) -> int: n = len(arr) # dp[i]记录从第i个元素(包含第i个)往前找到的和为target最短子数组长度 dp = [float("inf")] * n sums, ans = 0, float("inf") # sum_record记录和为target的子数组位置 sum_record = {0: -1} for i, num in enumerate(arr): sums += num dp[i] = dp[i-1] if sums - target in sum_record: cur_len = i - sum_record[sums-target] if i - cur_len >= 0: ans = min(ans, cur_len + dp[i-cur_len]) dp[i] = min(dp[i-1], cur_len) sum_record[sums] = i return ans if ans != float("inf") else -1
leetcode-28双周赛-5428-找两个和为目标值且不重叠的子数组
原文：https://www.cnblogs.com/oldby/p/13129572.html