算法-面试题系列 - ??? 数组累加和问题三连 ???

题目一

arr[]数组，数组元素全部都是正数，给定sum

求数组元素累加后和为sum子数组的最长的数组个数

例如，arr [3,2,1,1,1,6,1,1,1,1,1,1]

[3,2,1] [6] [1,1,1,1,1,1] 累加和都为6 最长的数组长度为6

答案：6

思路

数组累加和问题 存在单调性 数组窗口变大，和变大，窗口减小，和减小的

这种单调性 可以使用滑动窗口 双指针的方式来尝试

• WS <Sum R++
• WS >Sum, L++
• WS==Sum, R++

image-20210604203802202

情况一：WS <Sum R++

image-20210604203922393

情况二：WS >Sum L++

image-20210604204105619

image-20210604204208093

情况三：WS ==Sum R++

image-20210604204415637

image-20210604204602269

public static int getMaxLength(int[] arr, int sum) {
        if (arr == null || arr.length == 0 || sum <= 0) {
            return 0;
        }
        int left = 0;
        int right = 0;
        int wsum = arr[0];//[0,0] wsum=arr[0]
        int len = 0;
        while (right < arr.length) {
            if (wsum == sum) {
                len = Math.max(len, right - left + 1);//sum==wsum更新len
                wsum -= arr[left++];
            } else if (wsum < sum) {
                right++;
                if (right == arr.length) {
                    break;
                }
                wsum += arr[right];
            } else {
                wsum -= arr[left++];
            }
        }
        return len;
    }

题目二

arr[]数组，数组元素整数(负数，0 正数)，给定sum

求数组元素累加后和为sum子数组的最长的数组个数

思路

和题目一，修改了数组元素的属性，单调性消失，串口增大 ，子数组的累加和可能变小和增大都有可能，不具备单调性题解。

两个套路

1、子数组以index开头，求答案。 最大的答案必在其中

2、子数组以index结尾，求答案。最大的答案必在其中

image-20210604211225466

index=0

image-20210604212302729

index=1

image-20210604212634138

index=2 找到答案情况

image-20210604213107282

public static int maxLength(int[] arr, int k) {
   if (arr == null || arr.length == 0) {
      return 0;
   }
   HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
   map.put(0, -1); // important 0累加和为-1 不能少，不然会错过0-index wsum==sum的情况
   int len = 0;
   int sum = 0;
   for (int i = 0; i < arr.length; i++) {
      sum += arr[i];//sum为0到index的累加和
      if (map.containsKey(sum - k)) {
         len = Math.max(i - map.get(sum - k), len);//有前缀和  len= i - map.get(sum - k)
      }
      if (!map.containsKey(sum)) {
         map.put(sum, i);//不存在前缀和，放入hashmap
      }
   }
   return len;
}

题目二变体

arr[]数组，数组元素为整数(负数，0 正数)。

求子数组中含有相同个数的1和2的最长子数组 [1,1,3,3,3,3,2,2] 数组中有两个1和2 ，子数组达标，长度为8

题目三

arr[]数组，数组元素为整数(负数，0 正数)。给定累加和sum

求 子数组累加和小于等于sum 的最长子数组长度