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 的子数组。

提示：

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

解题思路

这道题要求找两个不重叠且和为目标值的子数组，使得它们的长度和最小。

核心思路：

  1. 使用滑动窗口找出所有和为target的子数组及其位置
  2. 对于每个分割点i，计算左半部分[0,i-1]和右半部分[i,n-1]中最短子数组的长度
  3. 枚举所有可能的分割点，找到最小的长度和

具体实现：

  1. 先用滑动窗口技术找出每个位置开始的最短子数组长度（和为target）
  2. 构建prefix数组：prefix[i]表示在位置i之前（不包括i）的最短子数组长度
  3. 构建suffix数组：suffix[i]表示从位置i开始（包括i）的最短子数组长度
  4. 遍历所有分割点，计算prefix[i] + suffix[i]的最小值

时间优化： 可以在一次遍历中同时维护前缀最小值和计算结果，避免额外的数组存储。

这种方法的关键在于如何高效地找到每个位置对应的最短子数组，以及如何维护前缀和后缀的最小值信息。

代码实现

class Solution {
public:
    int minSumOfLengths(vector<int>& arr, int target) {
        int n = arr.size();
        vector<int> best(n, INT_MAX); // best[i] 表示从位置i开始的最短子数组长度
        
        // 使用滑动窗口找出每个起始位置的最短子数组
        int left = 0, sum = 0;
        for (int right = 0; right < n; right++) {
            sum += arr[right];
            while (sum > target && left <= right) {
                sum -= arr[left++];
            }
            if (sum == target) {
                best[left] = min(best[left], right - left + 1);
            }
        }
        
        // 从右向左更新best数组，保存从每个位置开始的最短长度
        for (int i = n - 2; i >= 0; i--) {
            best[i] = min(best[i], best[i + 1]);
        }
        
        int result = INT_MAX;
        left = 0, sum = 0;
        
        // 再次使用滑动窗口，对于每个找到的子数组，查看其右侧是否有合适的子数组
        for (int right = 0; right < n; right++) {
            sum += arr[right];
            while (sum > target && left <= right) {
                sum -= arr[left++];
            }
            if (sum == target && right + 1 < n && best[right + 1] != INT_MAX) {
                result = min(result, right - left + 1 + best[right + 1]);
            }
        }
        
        return result == INT_MAX ? -1 : result;
    }
};

class Solution:
    def minSumOfLengths(self, arr: List[int], target: int) -> int:
        n = len(arr)
        best = [float('inf')] * n  # best[i] 表示从位置i开始的最短子数组长度
        
        # 使用滑动窗口找出每个起始位置的最短子数组
        left = 0
        current_sum = 0
        for right in range(n):
            current_sum += arr[right]
            while current_sum > target and left <= right:
                current_sum -= arr[left]
                left += 1
            if current_sum == target:
                best[left] = min(best[left], right - left + 1)
        
        # 从右向左更新best数组，保存从每个位置开始的最短长度
        for i in range(n - 2, -1, -1):
            best[i] = min(best[i], best[i + 1])
        
        result = float('inf')
        left = 0
        current_sum = 0
        
        # 再次使用滑动窗口，对于每个找到的子数组，查看其右侧是否有合适的子数组
        for right in range(n):
            current_sum += arr[right]
            while current_sum > target and left <= right:
                current_sum -= arr[left]
                left += 1
            if current_sum == target and right + 1 < n and best[right + 1] != float('inf'):
                result = min(result, right - left + 1 + best[right + 1])
        
        return -1 if result == float('inf') else result

public class Solution {
    public int MinSumOfLengths(int[] arr, int target) {
        int n = arr.Length;
        int[] best = new int[n];
        Array.Fill(best, int.MaxValue);
        
        // 使用滑动窗口找出每个起始位置的最短子数组
        int left = 0, sum = 0;
        for (int right = 0; right < n; right++) {
            sum += arr[right];
            while (sum > target && left <= right) {
                sum -= arr[left++];
            }
            if (sum == target) {
                best[left] = Math.Min(best[left], right - left + 1);
            }
        }
        
        // 从右向左更新best数组，保存从每个位置开始的最短长度
        for (int i = n - 2; i >= 0; i--) {
            best[i] = Math.Min(best[i], best[i + 1]);
        }
        
        int result = int.MaxValue;
        left = 0;
        sum = 0;
        
        // 再次使用滑动窗口，对于每个找到的子数组，查看其右侧是否有合适的子数组
        for (int right = 0; right < n; right++) {
            sum += arr[right];
            while (sum > target && left <= right) {
                sum -= arr[left++];
            }
            if (sum == target && right + 1 < n && best[right + 1] != int.MaxValue) {
                result = Math.Min(result, right - left + 1 + best[right + 1]);
            }
        }
        
        return result == int.MaxValue ? -1 : result;
    }
}

/**
 * @param {number[]} arr
 * @param {number} target
 * @return {number}
 */
var minSumOfLengths = function(arr, target) {
    const n = arr.length;
    const leftMin = new Array(n).fill(Infinity);
    let left = 0, sum = 0, minLen = Infinity, result = Infinity;
    
    // First pass: find minimum length subarray ending at or before each position
    for (let right = 0; right < n; right++) {
        sum += arr[right];
        
        while (sum > target) {
            sum -= arr[left];
            left++;
        }
        
        if (sum === target) {
            const len = right - left + 1;
            minLen = Math.min(minLen, len);
        }
        
        leftMin[right] = minLen;
    }
    
    // Second pass: find minimum length subarray starting at each position
    left = n - 1;
    sum = 0;
    minLen = Infinity;
    
    for (let right = n - 1; right >= 0; right--) {
        sum += arr[right];
        
        while (sum > target) {
            sum -= arr[left];
            left--;
        }
        
        if (sum === target) {
            const len = left - right + 1;
            minLen = Math.min(minLen, len);
            
            // Check if we can combine with a subarray from the left
            if (right > 0 && leftMin[right - 1] !== Infinity) {
                result = Math.min(result, len + leftMin[right - 1]);
            }
        }
    }
    
    return result === Infinity ? -1 : result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度大小说明
时间复杂度O(n)需要遍历数组两次，每次都是O(n)的滑动窗口操作
空间复杂度O(n)需要额外的best数组来存储每个位置的最短子数组长度

相关题目