[LeetCode] Find Two Non-overlapping Sub-arrays Each With Target Sum

1477. Find Two Non-overlapping Sub-arrays Each With Target Sum

Given an array of integers arr and an integer target.

You have to find two non-overlapping sub-arrays of arr each with sum equal target. There can be multiple answers so you have to find an answer where the sum of the lengths of the two sub-arrays is minimum.

Return the minimum sum of the lengths of the two required sub-arrays, or return -1 if you cannot find such two sub-arrays.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
bool isMatch(const pair<int, int>& p1, const pair<int, int>& p2) {
if(p1.first < p2.first) {
return p1.second < p2.first;
} else {
return p2.second < p1.first;
}
}
public:
int minSumOfLengths(vector<int>& arr, int target) {
int start = 0, end = 0, sum = arr[0], sz = arr.size() - 1;
map<int, list<pair<int, int>>> subArray;
while(end != sz || sum >= target) {
if(sum < target && end != sz) {
sum += arr[++end];
} else if(sum > target && start != sz) {
if(start != end)
sum -= arr[start++];
else
sum += arr[++end] - arr[start++];
} else if(sum == target){
subArray[end - start + 1].push_back({start, end});
if(end != sz)
sum += arr[++end];
else
break;
} else
break;
}

int res = INT_MAX;
for(auto arrayA = begin(subArray); arrayA != subArray.end() && arrayA->first * 2 < res; arrayA++) {
for(auto pairA = begin(arrayA->second); pairA != arrayA->second.end() && arrayA->first * 2 < res; pairA++) {
for(auto arrayB = arrayA; arrayB != subArray.end() && arrayB->first + arrayA->first < res; arrayB++) {
for(auto pairB = arrayA->first == arrayB->first ? next(pairA) : begin(arrayB->second); pairB != arrayB->second.end() && arrayB->first + arrayA->first < res; pairB++) {
if(isMatch(*pairA, *pairB)) {
res = min(res, arrayA->first + arrayB->first);
}
}
}
}
}

return res == INT_MAX ? -1 : res;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2021/03/09/PS/LeetCode/find-two-non-overlapping-sub-arrays-each-with-target-sum/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.