找两个和为目标值且不重叠的子数组

标签: 数组 哈希表 二分查找 动态规划 滑动窗口

难度: Medium

给你一个整数数组 arr 和一个整数值 target 。

请你在 arr 中找 两个互不重叠的子数组 且它们的和都等于 target 。可能会有多种方案，请你返回满足要求的两个子数组长度和的 最小值 。

请返回满足要求的最小长度和，如果无法找到这样的两个子数组，请返回 -1 。

示例 1：

输入：arr = [3,2,2,4,3], target = 3
输出：2
解释：只有两个子数组和为 3 （[3] 和 [3]）。它们的长度和为 2 。

示例 2：

输入：arr = [7,3,4,7], target = 7
输出：2
解释：尽管我们有 3 个互不重叠的子数组和为 7 （[7], [3,4] 和 [7]），但我们会选择第一个和第三个子数组，因为它们的长度和 2 是最小值。

示例 3：

输入：arr = [4,3,2,6,2,3,4], target = 6
输出：-1
解释：我们只有一个和为 6 的子数组。

示例 4：

输入：arr = [5,5,4,4,5], target = 3
输出：-1
解释：我们无法找到和为 3 的子数组。

示例 5：

输入：arr = [3,1,1,1,5,1,2,1], target = 3
输出：3
解释：注意子数组 [1,2] 和 [2,1] 不能成为一个方案因为它们重叠了。

提示：

  • 1 <= arr.length <= 10^5
  • 1 <= arr[i] <= 1000
  • 1 <= target <= 10^8

Submission

运行时间: 134 ms

内存: 29.4 MB

class Solution:
    def minSumOfLengths(self, arr: List[int], target: int) -> int:
        q = deque()
        mn = inf
        ans = inf
        left = right = total = 0
        n = len(arr)
        while right<n:
            #移动有边界
            while right<n and total<target:
                total+=arr[right]
                right+=1
            #移动左边界
            while total>target:
                total-=arr[left]
                left+=1
            #目标值等于total
            if total==target:
                #删除不重复区间 并记录最小长度
                while q and q[0][1]<=left:
                    l,r=q.popleft()
                    mn=min(mn,r-l)

                #如果有不重叠在前 个更新答案
                if mn!=inf:
                    ans=min(ans,mn+right-left)
                # 如果一个区间还不如最小区间短，那就不用加入q
                if right-left<mn:
                    q.append((left,right))
                total-=arr[left]
                left+=1
        return -1 if ans== inf else ans

Explain

此题解采用了双指针和滑动窗口的方法来找到和为target的子数组。利用left和right指针控制窗口的左右边界。当窗口内元素之和小于target时右移right扩大窗口；当窗口内之和大于target时，右移left缩小窗口。每次窗口内之和等于target时，检查是否存在之前记录的非重叠子数组，如果存在，则更新可能的最小长度。为了记录和跟踪非重叠的子数组，使用deque（双端队列）来存储每个有效的子数组的起始和终止位置，并维护一个最小长度变量。当发现更短的子数组时，更新此最小值。最终，如果有符合条件的两个子数组，返回它们长度之和的最小值；否则返回-1。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def minSumOfLengths(self, arr: List[int], target: int) -> int:
        q = deque() # 存储满足条件的子数组的起止位置
        mn = inf # 记录非重叠子数组中的最小长度
        ans = inf # 记录最终的最小长度和
        left = right = total = 0
        n = len(arr)
        while right<n:
            while right<n and total<target:
                total+=arr[right] # 扩大窗口
                right+=1
            while total>target:
                total-=arr[left] # 缩小窗口
                left+=1
            if total==target:
                while q and q[0][1]<=left:
                    l,r=q.popleft()
                    mn=min(mn,r-l) # 更新非重叠子数组的最小长度
                if mn!=inf:
                    ans=min(ans,mn+right-left) # 更新最小长度和
                if right-left<mn:
                    q.append((left,right)) # 满足条件的子数组加入队列
                total-=arr[left]
                left+=1
        return -1 if ans== inf else ans

Explore

在算法中，通过使用双端队列deque来存储满足条件的子数组的起止位置，确保找到的两个子数组互不重叠。当找到一个新的和为target的子数组时，算法会检查deque中的子数组，如果队列中已有的子数组的结束位置小于或等于当前子数组的开始位置left，表明这两个子数组不重叠。这样，通过队列中存储的子数组的起止位置信息，可以有效地筛选并维护不重叠的子数组。

双端队列在算法中用于存储每个满足条件（和等于target）的子数组的起始和终止位置。这种存储方式方便了快速地添加新的子数组和移除旧的子数组。当发现新的满足条件的子数组时，算法会检查队列中是否有与当前子数组不重叠的子数组。如果有，算法会计算两个子数组长度之和并尝试更新最小长度和。此外，队列通过维护子数组的顺序，帮助快速地找到与当前子数组不重叠的最早的子数组，从而高效更新最小长度和。

这样做是为了确保队列中的子数组与当前考察的子数组不重叠。当窗口和等于目标值时，需要评估这个窗口与队列中已有的子数组是否重叠。移除所有结束位置小于等于当前左指针的子数组是因为这些子数组的有效性已经过时（它们的范围不可能与当前或未来的窗口重叠），清除这些子数组有助于保持队列的有效性和减少不必要的计算，同时确保我们只比较不重叠的子数组，以有效更新最小长度和。

移除结束位置小于等于当前left指针的子数组元素，是因为这些子数组已不可能与当前窗口或任何后续窗口形成不重叠的子数组组合。这种移除操作有助于维护一个干净且高效的队列状态，确保队列中只包含可能与当前或后续窗口组成有效组合的子数组。这样同时也简化了非重叠子数组最小长度mn的更新过程，因为我们只需考虑队列中剩余的有效子数组。