Find Two Non-overlapping Sub-arrays Each With Target Sum LeetCode solution in C++

1
class Solution {
2
 public:
3
  int minSumOfLengths(vector<int> &arr, int target) {
4
    map<int, int> prefix;
5
    int n = arr.size();
6
    vector<int> p(n), s(n);
7
    int currsum = 0;
8
    int ans = INT_MAX;
9
    for (int x = 0; x < n; x++) {
10
      currsum += arr[x];
11
      if (currsum == target)
12
        ans = min(ans, x + 1);
13
      else {
14
        if (prefix.find(currsum - target) != prefix.end()) {
15
          ans = min(ans, x - prefix[currsum - target]);
16
        }
17
      }
18
      prefix[currsum] = x;
19
      p[x] = ans;
20
    }
21
    map<int, int> suffix;
22
    currsum = 0;
23
    ans = INT_MAX;
24
    for (int x = n - 1; x >= 0; x--) {
25
      currsum += arr[x];
26
      if (currsum == target)
27
        ans = min(ans, n - x);
28
      else {
29
        if (suffix.find(currsum - target) != suffix.end()) {
30
          ans = min(ans, suffix[currsum - target] - x);
31
        }
32
      }
33
      suffix[currsum] = x;
34
      s[x] = ans;
35
    }
36
    ans = INT_MAX;
37
    for (int x = 1; x < n; x++) {
38
      if ((long long)p[x - 1] + s[x] < INT_MAX) ans = min(ans, p[x - 1] + s[x]);
39
    }
40
    if (ans == INT_MAX) return -1;
41
    return ans;
42
  }
43
};