X

LEETCODE 1477. Find Two Non-overlapping Sub-arrays Each With Target Sum 解题思路分析

题目大意:

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

给你一个整数数组 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

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1477

解题思路分析:

  1. 使用滑动窗口找到所有和为target的区间,并将区间信息保存至list
  2. 将list内区间按照长度排序
  3. 使用2层循环,两两比较每个区间,如果他们不重合,则使用他们的区间长度和更新全局最小值。(注意剪枝)

实现代码:

public int minSumOfLengths(int[] arr, int target) {
    int sum=0; // 区间和
    int left=0,right=0; // 区间左右指针
    List<int[]> list=new ArrayList<>(); // 记录所有和为target的区间
    while(right<arr.length){ // 滑动窗口来找到所有符合条件的区间
        sum+=arr[right]; // 累加区间和
        if(sum==target){ // 区间和等于target
            list.add(new int[]{left,right}); // 将当前区间存入list
        }else if(sum>target){ // 如果区间和大于target
            while(sum>target&&left<=right){ // 减少左区间以减少区间和
                sum-=arr[left];
                left++;
            }
            if(sum==target){ // 移动完左区间后,当前区间和等于target
                list.add(new int[]{left,right}); // 将当前区间存入list
            }
        }
        right++; // 移动右区间
    }
    if(list.size()<2) return -1; // 如果合理区间不足2个,返回-1。
    // 将所有区间按照区间长度排序
    Collections.sort(list,(int[] a,int[] b)->(a[1]-a[0])-(b[1]-b[0]));
    // 返回结果(最小区间和)
    int min=Integer.MAX_VALUE;
    // 循环每一个区间
    for(int i=0;i<list.size();i++){
        int[] arr1=list.get(i); // 当前区间
        int length1=arr1[1]-arr1[0]+1; // 当前区间长度
         // 当前区间长度大于返回结果,退出
         // 因为数组已排序,若当前区间长度大于等于min的话,后面的也一定大于
        if(length1>=min) break;
        for(int j=i+1;j<list.size();j++){  // 循环第二个区间
            int[] arr2=list.get(j); // 第二个区间
            int length2=arr2[1]-arr2[0]+1; // 第二个区间长度
            if(length1+length2>=min) break; // 2个区间长度和大于返回结果,退出当前循环
            if(!isOverlap(arr1,arr2)){ // 如果两个区间不重合,用区间长度和去更新min
                min=Math.min(min,length1+length2);
            }
        }
    }
    return min==Integer.MAX_VALUE?-1:min;
}

boolean isOverlap(int[] a,int[] b){
    return a[1]>=b[0]&&a[1]<=b[1] || a[0]>=b[0]&&a[0]<=b[1];
}

本题解法执行时间为31ms。

Runtime: 31 ms, faster than 66.57% of Java online submissions for Find Two Non-overlapping Sub-arrays Each With Target Sum.

Memory Usage: 95.6 MB, less than 100.00% of Java online submissions for Find Two Non-overlapping Sub-arrays Each With Target Sum.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1477-find-two-non-overlapping-sub-arrays-each-with-target-sum-解题思路分析/
Categories: leetcode
kwantong: