DP on single sub array of min length 
Intuition

The original question, P2, asks for two non overlapping sub arrays with target sum, with optimal (minimum) total size. This can actually be converted
# Intuition
- The original question, `P2`, asks for two non overlapping sub arrays with target sum, with optimal (minimum) total size. This can actually be converted to a DP for a single sub array with min length, `P1`. 
- Consider the solution to `P2` being `[a, b)` and `[c, d)`. 
- This is a subproblem `P2` on `arr[0, d)`, with 2nd sub array ending on last element, **and** it is obvious that `[a,b)` is an optimal solution to `P1` of `arr[0, c)`. 
- To find a valid sub array, do these 3 things
- - prefix sum `psum`
- - hash map `psum` to vector of `index` in increasing order
- - On `psum[j]` looks for the last `index` `i` in the hash map of `psum[i] - target`: `[i, j]` is an valid sub array ending in `j`
- The found valid sub array `[i,j]`, or `[i, j+1)`, is also used to update solution of `P1` at `arr[0, j+1)`
- Update the solution to `P2`, at each step `psum[j]`, using `[i, j]` as 2nd sub array, and optimal single sub array of `P1` in `arr[0, i)` as 1st sub array.

 

# Complexity
- Time complexity:
`O(N log N)`

 

# Code
```cpp []
class Solution {
public:
    int minSumOfLengths(vector<int>& arr, int target) {
        partial_sum(arr.begin(), arr.end(), arr.begin());
        unordered_map<int, vector<int>> psum2index; // prefix sum -> indices in ascending order
        vector<int> dp(arr.size()+1, 1'000'000);    // dp[i]: min len target sum sub array in arr[0, i)
        int ans = 1'000'000;
        psum2index[0] = {-1};
        for(int last = -1, j = 0; j < arr.size(); ++j) {
            psum2index[arr[j]].push_back(j);
            dp[j+1] = dp[j];
            if(auto itr = psum2index.find(arr[j] - target); itr != psum2index.end()) {
                int i =  itr->second.back() + 1; // found [i,j+1)
                dp[j+1] = min(dp[j+1], j+1-i);
                ans = min(ans, dp[i] + j+1-i);
            }
        }
        return ans == 1'000'000 ? -1 : ans;
    }
};
```
['C++']