@[TOC](这里写目录标题)
# 1、和为k的子数组的最大长度，数组中的元素可正、可负、可0
思路：假设存在和为k的最长子数组，索引范围`i~j`，那么下面的式子必然存在：

`k = 子数组[0~j]的和 - 子数组[0~i]的和 `

因此我们可以遍历数组求子数组[0~i]{0 < i < n}的累加和，**每次获取了累加和后就可以判断有没有以i结尾的和为k的子数组**，如果有则更新最大子数组的长度， 这个过程中除了要记录子数组[0~i]的累加和还要记录该位置的索引，方便后续统计长。

代码演示：

```java
public class LongestSumSubArrayLength {
    public int maxLength(int[] nums, int k){
        int max = 0;
        int sum = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        //如果不添加会忽略掉从0开始的子数组
        map.put(0, -1);
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (map.containsKey(sum - k)) {
                max = Math.max(max, i - map.get(sum - k));
            }
            //如果存在就保存该sum的最小索引,选择保存最小的位置
            if (!map.containsKey(sum)) {
                map.put(sum, i);
            }
        }
        return max;
    }
}
```

# 2、和为k的子数组的最大长度，数组中的元素都是正数

思路：由于题目的数据样本存在特殊性，因此我们除了可以用上面第一题的解法一位，我们还可以用数组中元素全是正数的特性，利用滑动窗口进行求解。

遍历数组arr过程中，用两个指针`l`和`r`维护滑动窗口的两端，窗口中的元素的和记为`sum`，滑动窗口的维护原则：

- 当`sum < k`，那么让sum+=arr[++r]
- 当`sum > k`，那么让sum-=arr[l++]，但是r不动，表示以`l`开头的子数组的可能性结束
- 当`sum = k`，存在一种答案了，比较并更新最大长度，并且让sum-=arr[l++]，因为数组中全是正数，下一次必然会进入第二种情况，做sum-=arr[l++]可以省去一次循环判断。

代码演示：

```java
public class LonggestSumSubArrayLengthInPositiveArray {
    public static int getMaxLength(int[] arr, int aim) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int l = 0;
        int r = 0;
        int maxLength = 0;
        int sum = arr[0];
        while(r < arr.length){
            //  r代表滑动窗口的有边界，根据滑动窗口中值的大小，来判断是移动l还是r
            if (sum == aim) {
                maxLength = Math.max(maxLength, r - l + 1);
                sum -= arr[l++];
            }else if (sum < aim) {
                r++;
                //避免数组越界
                if (r >= arr.length) {
                    break;
                }
                sum += arr[r];
            }else{
                sum -= arr[l++];
            }
        }
        return maxLength;
    }
}
```

# 3、和小于等于k的子数组的最大长度，数组中的元素可正、可负、可0
## 解法一
**动态规划 + 二分查找**

思路：

假设在[i~j]上存在和小于等于k的子数组，那么那么

`子数组[0~j]的和 - 子数组[0~i]的和 <= k`

我们想让[i~j]的长度尽可能的大，那么就要在`子数组[0~i]的和 >=子数组[0~j]的和  - k`成立的条件下让`i`尽可能地小。

遍历数组，每次判断`子数组[0~j]的和` 、 `子数组[0~i]的和` 和 `k`这三个变量之间的关系，更新最大符合条件的子数组的长度。

我们可以用一个数组h保存原数组[0~j]范围内的子数组和最大的值，数组是递增的，我们可以**通过数组h来找到尽可能小的i， 从而让[i~j]的范围尽可能的大**，查找的过程可以使用**二分法加速**。

代码演示：

```java
public class LonggestSubArrayLessSum {
	public static int maxLength(int[] arr, int k) {
        int[] h = new int[arr.length + 1];
        int sum = 0;
        //important 让h[0] = 0，不错过从第一个元素开始的答案
        h[0] = sum;
        for (int i = 0; i != arr.length; i++) {
            sum += arr[i];
            //h[i]保存了原数组0~i-1位置上子数组累加和能达到的最大的值，数组是递增的，h[i] >= h[i - 1]
            h[i + 1] = Math.max(sum, h[i]);
        }
        sum = 0;
        int res = 0;
        int pre = 0;
        int len = 0;
        for (int i = 0; i != arr.length; i++) {
            sum += arr[i];
            //sum = sub + k;
            pre = getLessIndex(h, sum - k);
            len = pre == -1 ? 0 : i - pre + 1;
            res = Math.max(res, len);
        }
        return res;
    }
    public static int getLessIndex(int[] arr, int num) {
        int low = 0;
        int high = arr.length - 1;
        int mid = 0;
        int res = -1;
        while (low <= high) {
            mid = (low + high) / 2;
            //找到大于等于num的最左位置，大于等于num保证了子数组的和<=k，找到最左位置，可以让子数组的长度尽量地大
            if (arr[mid] >= num) {
                res = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return res;
    }
}
```

## 解法二
**动态规划 + 滑动窗口**

思路：生成**以每个位置为起点的子数组的最小和**以及**这个子数组的结束位置**（包括在子数组内），然后用滑动窗口遍历以每个位置开头的子数组小于aim的最大长度，**用之前生成的信息加速r右移动的过程**。

生成辅助信息的过程可以从后往前遍历快速生成。

生成辅助信息是一次遍历得到，用滑动窗口枚举答案可能时，因为r一直往右不回退，因此**时间复杂度是O(N)的**。

代码演示：

```java
public class LonggestSubArrayLessSum {
    public static int maxLengthAwesome(int[] arr, int aim) {
        int length = arr.length;
        //保存以i位置为起点的子数组和的最小值
        int[] min = new int[length];
        //保存以i位置为起点的最小和子数组的右边界索引
        int[] minIndex = new int[length];
        min[length - 1] = arr[length - 1];
        minIndex[length - 1] = length - 1;
        //从后往前动态规划，生成以每个位置开头的子数组的和的最小值，以及对应的右边界的索引
        for (int i = length - 2; i >= 0; i--) {
            if (min[i + 1] <= 0) {
                min[i] = arr[i] + min[i + 1];
                minIndex[i] = minIndex[i + 1];
            } else {
                min[i] = arr[i];
                minIndex[i] = i;
            }
        }
        int r = 0;
        //动态记录start~end窗口内子数组的和
        int sum = 0;
        int len = 0;
        //遍历以每个位置开头的可以生成的和小于aim的最长的子数组，在这个过程找到子数组的最大长度
        for (int start = 0; start < length; start++) {
            //这个循环过程找到以start开头的小于aim的右边界
            while (r < length && sum + min[r] <= aim) {
                sum += min[r];
                r = minIndex[r] + 1;
            }
            //可能r仍然在原地，没有向右扩动，临界处理
            sum -= r > start ? arr[start] : 0;
            //更新最大长度
            len = Math.max(len, r - start);
            //r没有扩动的临界处理
            r = Math.max(start + 1, r);
        }
        return len;
    }
}
```

关于子数组求和的三种经典问题

总共已有 0 条评论