利用双指针枚举第二个和为target的区间,并将当前求得的区间信息(长度和结尾坐标)存入队列中,作为第一个区间的信息。
typedef pair<int, int> PII;
const int INF = 1e9;
class Solution {
public:
int minSumOfLengths(vector<int>& arr, int target) {
int n = arr.size();
int len1 = INF, ans = INF, sum = 0;
queue<PII> q;
for (int i = 0, j = 0; i<n; i++){
sum += arr[i];
while (j < n && sum > target) sum -= arr[j++];
if (sum == target){
int len2 = i - j + 1;
while (q.size() && q.front().first < j){
len1 = min(len1, q.front().second);
q.pop();
}
ans = min(ans, len1 + len2);
q.push({i, len2});
}
}
return ans >= INF ? -1 : ans;
}
};