1. 累加和等于k的最长子数组（正数）

1.1 题目

给定一个数组arr，该数组无序，但每个值均为正数，再给定一个正数k，求arr的所有子数组中所有元素相加和为k的最长子数组

1.2 思路

滑动窗口，[left ... right],

如果sum < k, right ++
如果sum >k, left ++
如果sum == k, 收集信息，left++

1.3 实现

    public int getMaxLength(int[]arr, int k){
        if(arr == null || arr.length == 0){
            return -1;
        }
        int left = 0;
        int right = 0;
        int sum = arr[0];
        int maxLength = -1;
        while (right < arr.length){
            if(sum == k){
                maxLength = Math.max(maxLength, right - left + 1);
                sum -= arr[left];
                left++;
            }else if(sum > k){
                sum -= arr[left];
                left++;
            }else {
                right++;
                if(right == arr.length){
                    break;
                }
                sum += arr[right];
            }
        }
        return maxLength;
    }

2. 累加和等于k的最长子数组（包含正数、负数、零）

2.1 题目

给定一个数组arr，该数组无序，其中有正数、负数或者为零，再给定一个k，求arr的所有子数组中所有元素相加和为k的最长子数组

2.2 思路

前缀和记录

遍历原数组，将前缀和和下边记录在map中，即为map<sum，i>，如果有相同的前缀数组，那么只保留第一个下标（这样结果会最长）
重新遍历数组，cur当前遍历的位置，s1当前位置的累加和，max为等于k的最长子数组的长度
然后去前缀数组中找s1-k的有没有对应的记录
1. 如果有：index = map.get(s1-k), max = Math.max(i-index. max)
2. 没有，继续遍历

2.3 实现


    public static int maxSubArrayLen(int[] arr, int k) {
        if (arr == null) {
            return 0;
        }
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        int ans = 0;
        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
            // 期待map里面有sum - k的记录
            if (map.containsKey(sum - k)) {
                ans = Math.max(ans, i - map.get(sum - k));
            }
            if (!map.containsKey(sum)) {
                map.put(sum, i);
            }
        }
        return ans;
    }

3.累加和小于或者等于k的最长数组长度

3.1 题目

给定一个数组arr，该数组无序，其中有正数、负数或者为零，再给定一个k，求arr的所有子数组中所有元素相加和小于或者等于k的最长子数组

3.2 思路

2个辅助数组
1. minSums[i] 表示从i位置到结束的最小累加和
2. minSumEnds[i] 表示从i位置到结束的最小累加和，对应的右边界
遍历数组，构建辅助数组
1. 如果当前的下一个位置的最小累加和，小于零就扩张，即minSums[i+1]<0
2. 如果大于等于零，不需要扩张记录当前即可值即可
遍历数组，从头开始，sum累加找下一块加起来还小于等于k，一直扩张区域

3.3 实现

    public static int maxSubArrayLen112123(int[] arr, int k){
        if(arr == null || arr.length == 0){
            return -1;
        }
        int[] minSums = new int[arr.length];
        int[] minSumEnds = new int[arr.length];
        minSums[arr.length-1] = arr[arr.length-1];
        minSumEnds[arr.length-1] = arr.length-1;
        for (int i = arr.length-2; i <=0 ; i--) {
            //小于才去扩minSum
            if(minSums[i+1] < 0){
                minSums[i] = arr[i] + minSums[i+1];
                minSumEnds[i] = minSums[i+1];
            }else{
                //大于就是当前值和下标
                minSums[i] = arr[i];
                minSumEnds[i] = i;
            }
        }

        int end = 0;
        int sum = 0;
        int res = 0;
        for (int i = 0; i < arr.length; i++) {
            //从0开始，sum累加找下一块加起来还小于等于k，一直扩张区域
            while (end < arr.length && sum + minSums[end] <= k){
                sum += minSums[end];
                end = minSumEnds[end] + 1;
            }
            res = Math.max(res, end - i);
            if(end > i){
                //窗口还有数
                sum -= arr[i];
            }else{
                //窗口内已经没数了，证明从i开头的所有子数组累加和都不可能<=k
                end = i + 1;
            }
        }

        return res;
    }

累加和为k的最长子数组