LeetCode 1477 找两个和为目标值且不重复的子数组
🟠 中等偏上
https://leetcode.cn/problems/find-two-non-overlapping-sub-arrays-each-with-target-sum/description/
方法一：前缀和+hash_table（任意数据） 方法二：滑动窗口（只适用于正数）
题解
使用滑动窗口找到所有合法位置。同时更新res。
类似于求数组中两个数的最小和一样，使用 O(n) 的时间复杂度即可：维护一个值表示前面的最小值，每次更新它。
本也想用一个数更新前面的最小长度，但是处理重复很复杂，使用数组更加方便的利用left巧妙防止重叠。
pre数组中的每个位置应该每次都更新，只是更新的值会发生变化，因此设置一个数 min_len维护每次设置的新值，每层循环都要更新pre[i] ，min_len 在找到目标子数组后更新。
res 更新在找到目标子数组后进行更新，但是由于使用的变量可能越界，因此要设置条件保证不越界。
class Solution {
public:
int minSumOfLengths(vector<int>& arr, int target) {
vector<int> pre(arr.size(),INT_MAX); // pre[i] 到i-1或之前的最短的合法子数组长度。
int left = 0;
int sum = 0;
int min_len = INT_MAX;
int res = INT_MAX;
for(int i = 0;i<arr.size();i++){
sum+=arr[i];
while(sum>target){
sum-=arr[left];
left++;
}
if(sum==target){
min_len = min(i-left+1,min_len);
//已经有一个合法的组数组之后再更新res，防止下面的逻辑出问题
if(left>0&&pre[left-1]!=INT_MAX){
res = min(res,i-left+1+pre[left-1]);
}
}
pre[i] = min_len;
}
return res==INT_MAX?-1:res;
}
};