Simple O(n) C++ Solution ✅ | Prefix Sum | Single Iteration 🔥✅
IntuitionWe begin by selecting the first subarray that meets the required sum. We then track the shortest subarray length found so far. Each time we discover a
# Intuition

We begin by selecting the first subarray that meets the required sum. We then track the shortest subarray length found so far. Each time we discover a new subarray, we update our answer if the new length is smaller, storing the best length for future comparisons.

# Approach

**1. Initialization:**

- Create a `best` array to store the best lengths of subarrays that sum up to the target at each index.
- Initialize `sum` to accumulate the current sum of elements.
- Set `ans` to a large value (e.g., `INT_MAX`) to track the minimum length found.
- Use `curr` to keep track of the current subarray length.

---

**2. Iterate through the array:**

- For each element `arr[i]`:
  - Add `arr[i]` to `sum`.
  - Increment `curr` (current length of the subarray).

**Adjust the window:**

- While `sum` exceeds the target:
  - Subtract elements from the start of the subarray until `sum` is less than or equal to the target.

**Check for valid subarray:**

- If `sum` equals the target:
  - Check if there exists a previous subarray with a valid length:
    - If `best[s-1]` (where `s` is the starting index of the current subarray) is not `INT_MAX`, update `ans`:
      - `ans = min(ans, best[s-1] + curr)`, where `curr` is the current length of the subarray.

- Update `best`:
  - `best[i] = min(best[i], curr)` to store the best length found up to the current index.

---

**3. Final Result:**

- After iterating through the entire array:
  - If `ans` is still `INT_MAX`, it means no valid subarray was found.
  - Otherwise, `ans` contains the minimum length of the subarray that sums to the target.


# Complexity
- Time complexity:
$$O(n)$$

- Space complexity:
$$O(n)$$

# Code
```cpp []
class Solution {
public:
    int minSumOfLengths(vector<int>& arr, int target) {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);
        int sum = 0; int s = 0; int n = arr.size();
        int curr = INT_MAX; int ans = INT_MAX;
        vector<int>best(n, INT_MAX);

        for(int i = 0; i<n; i++){
            sum += arr[i];
            while(sum > target) sum -= arr[s++];
            if(sum == target){
                if(s > 0 && best[s-1] != INT_MAX){
                    ans = min(ans , best[s-1] + i - s + 1);
                }
                curr = min(curr , i - s + 1);
            }
            best[i] = curr;
        }
        return ans == INT_MAX ? -1 : ans;
    }
};
```
['C++']