力扣 LeetCode 1477. 找两个和为目标值且不重叠的子数组 - 力扣（LeetCode） 1477. 找两个和为目标值且不重叠的子数组 - 给你一个整数数组 arr 和一个整数值 target 。 请你在 arr 中找 两个互不重叠的子数组 且它们的和都等于 target 。可能会有多种方案，请你返回满足要求的两个子数组长度和的 最小值 。 请返回满足要求的最小长度和，如果无法找到这样的两个子数组，请返回 -1 。   示例 1： 输入：arr = [3,2,2,4,3], target = 3 输出：2 解释：只有两个子数组和为 3 （[3] 和 [3]）。它们的长度和为... 思路 递推+滑动窗口。首先要求子数组的和，肯定滑动窗口比较合适。然后要记录当前滑动窗口不重叠的最小长度，可以用递推/动规。 len = right - left ans=Min(ans, dp[left] + len) dp[right]=Min(dp[right-1], len) 代码 class Solution { public int minSumOfLengths(int[] arr, int target) { int n = arr.length; int[] dp = new int[n + 1]; dp[0] = Integer.MAX_VALUE; int ans = Integer.MAX_VALUE; int sum = 0; int left = 0, right = 0; while (right < arr.length) { sum += arr[right++]; while (sum > target) { sum -= arr[left++]; } dp[right] = dp[right - 1]; if (sum == target) { int len = right - left; if (dp[left] != Integer.MAX_VALUE) { ans = Math.min(ans, dp[left] + len); } dp[right] = Math.min(dp[right], len); } } return ans == Integer.MAX_VALUE ? -1 : ans; } } 1 个帖子 - 1 位参与者 阅读完整话题

  • 情报分类：综合情报
  • 分类依据：内容未命中明确的垂直分类规则，归入综合情报
  • 信息来源：服务器 / LINUX DO - 最新话题
  • 发布时间：2026/9/17 09:29:05