当前位置：首页 > news >正文

【C++二分查找】1477. 找两个和为目标值且不重叠的子数组|1850

news 2025/6/7 3:28:28

本文涉及的基础知识点

C++二分查找
C++算法：滑动窗口总结
C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例包括课程视频
C++前后缀分解

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

给你一个整数数组 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⁵
1 <= arr[i] <= 1000
1 <= target <= 10⁸

二分查找

一，计算前缀和。
二，枚举所有和为target的子数组v,每个元素记录[开始，长度]。方法a:滑动窗口，时间复杂度O(n)。方法b:二分查找，前缀和，枚举right。时间复杂度：O(nlogn)。由于arr[i]>0，所以如果[l1,r1][l2,r2]符合，且r1 == r2，则l1 == l2。
三，枚举v中各元素，iMin记录当前元素之前的元素的最小元素长度。ret = min(ret,iMin+当前元素长度)。滑动窗口v[0…j-1]是所有和v[i]不重叠且在其左边的子数组。

前后缀分解+二分查找

pre[i]记录长度为i的前缀中和为target的最短子数组，如果不存在，则值为N+1。suff[i]记录长度为i的后缀的合法子数组最短长度。
min(pre[i]+suff[N-i])就是答案，i $\in$ [0,N]。
计算前后缀可以封装成函数Pre，参数转置以下就可以了。
preSum记录前缀和。
通过i枚举，子数组的最后一个元素，看是否存在 preSum[j] = preSum[i+1]-target，如果存在arr[j…i]就是合法子数组。因为arr[i]>0，故顶多只有一个合法j。

代码

核心代码

class Solution {public:int minSumOfLengths(vector<int>& arr, int target) {vector<int> preSum(1);for (const auto& n : arr) {preSum.emplace_back(n + preSum.back());}vector<pair<int, int>> v;for (int i = 0; i < arr.size(); i++) {auto it = std::equal_range(preSum.begin(), preSum.end(), preSum[i+1] - target);const int len = it.second - it.first;if (1 == len ) {const int left = it.first- preSum.begin();v.emplace_back(left, i+1-left);}}int iMin = 1000'000;int iRet = iMin;for (int i = 0, j = 0; i < v.size(); i++) {while ((j < v.size()) && (v[j].first + v[j].second <= v[i].first)) {iMin = min(iMin, v[j].second);j++;}iRet = min(iRet, iMin+v[i].second);}return (iRet > arr.size()) ? -1 : iRet;}};

单元测试

class Solution {public:int minSumOfLengths(vector<int>& arr, int target) {vector<int> preSum(1);for (const auto& n : arr) {preSum.emplace_back(n + preSum.back());}vector<pair<int, int>> v;for (int i = 0; i < arr.size(); i++) {auto it = std::equal_range(preSum.begin(), preSum.end(), preSum[i+1] - target);const int len = it.second - it.first;if (1 == len ) {const int left = it.first- preSum.begin();v.emplace_back(left, i+1-left);}}int iMin = 1000'000;int iRet = iMin;for (int i = 0, j = 0; i < v.size(); i++) {while ((j < v.size()) && (v[j].first + v[j].second <= v[i].first)) {iMin = min(iMin, v[j].second);j++;}iRet = min(iRet, iMin+v[i].second);}return (iRet > arr.size()) ? -1 : iRet;}};

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功