subarray, 联想到用前缀和解题

暴力解法
首先枚举终点能保证不漏方案，枚举i，然后找到符合方案的就记录下来，并记录长度存到map里，key是坐标index，枚举当前满足条件的并且在他前面的，对应的length 这样做法最坏是O(n方)
这里可以想到一个优化，因为只要找前面最小的，那只需要把最小的存下来就好了，可以根据前面的状态递推过来
并没有要把两个区间都输出出来，所以只需要把值求出来，想到的优化就是记录当前index下对应的前面的最小值

都是正数，前缀和数组成单调递增
用双指针可以优化
枚举i作为区间的后端点，j是满足s[i] - s[j] <= target 的最后一个j，随着j的index增加，对应的s[j]一定是在增加的。
找到离i最近的j能满足上面的条件，并且j只能往后走。
(要保存下来这个时候i对应的j， 那么对于i来说前面哪些区间能满足区间和是target， 并且还要是end 在j -1 及之前，这样才不会相交)
这样就想到用一个数组存下来这个index对应的这个index为结尾或这个index之前的前缀和是target的最小的长度
根据递推的思想
遍历到每个index=i时，如果index = i - 1的value 小于 i 能够找到target长度的区间并且长度小于index= i - 1的长度，那么就更新index=i为这个长度，否则就是index=i-1的长度
min_len 初始化为INF

class Solution {
public int minSumOfLengths(int[] arr, int target) {
int n = arr.length;
int INF = 0x3f3f3f3f;

    int[] min = new int[n + 1];
    min[0] = INF;
    int ans = INF;

    int s = 0; // 当前区间和
    //因为是递推的，所以前缀和不用算出来，用一个值维护就好了
    for(int i = 1, j = 1; i <= n; i++){
        s += arr[i - 1];
        while(j <= i && s > target){
            s -= arr[j - 1];
            j++;
        }

        //开始想到map存下来这两个坐标，如果是用map存，就要用二分优化，
        if(s == target){
            ans = Math.min(ans, i - j + 1 + min[j - 1]);
            min[i] = Math.min( i - j + 1, min[i - 1]);
        }else{
            min[i] = min[i - 1];
        }
    }

    if(ans == INF) return -1;
    return ans;

}

}