[TOC]
# 1 数组累加和问题三连
知识点补充：系统设计类题目
设计一个系统，该系统的功能是可以一直不停的提供不同的UUID，该UUID使用的极为频繁，比如全球卖西瓜的，每个西瓜子是一个UUID
> 思路，如果使用hashcode，有可能会产生碰撞。不使用hashcode，使用机器的ip或者mac地址加上纳秒时间，也不行，所有机器时间是否强同步
> 解决思路：定义一台服务器，对世界的国家进行分类，比如中国下是省份，美国下是州，英国下是邦。每一个国家向中央服务器要随机范围，中央服务器分配出去的是start和range。比如给中国分配的是start从1开始，range到100w,中国uuid不够用了，可以再向中央服务器要，分配后中央服务器的start要增大到已分配出去后的位置。其他国家类似
> 该设计师垂直扩展的技术，当前很多有事水平扩展，比如直接hashcode，random等。但有些场景适合用这种垂直扩展的解决方案
## 1.1 数组累加和问题
### 1.1.1 第一连例题
有一个全是正数的数组，和一个正数sum。求该数组的累加和等于sum的子数组多长。例如[3,2,1,1,1,6,1,1,1,1,1,1],sum等于6。最长的子数组为[1,1,1,1,1,1]返回长度6
> 由于是正数数组，累加和和范围具有单调性。对于具有单调性的题目，要么定义左右指针，要么定义窗口滑动
定义窗口window,windowSum初始为0。滑动的过程中：
1、如果windowSum小于sum，窗口右边界R向右移动一个位置；
2、如果windowSum大于sum，窗口左边界L向右移动一个位置；
3、如果windowSum等于sum，此时的窗口大小就是一个满足条件的子数组大小，决定是否要更新答案；
```Java
public class Code01_LongestSumSubArrayLengthInPositiveArray {
// 滑动窗口的表示
public static int getMaxLength(int[] arr, int K) {
if (arr == null || arr.length == 0 || K <= 0) {
return 0;
}
// 初始窗口位置[0,0],窗口当前只有第一个数
int left = 0;
int right = 0;
int sum = arr[0];
int len = 0;
while (right < arr.length) {
// 窗口的累加和sum等于我们的目标k。求窗口大小len
if (sum == K) {
len = Math.max(len, right - left + 1);
// 窗口累加和减去左窗口位置的值，左位置再出窗口
sum -= arr[left++];
} else if (sum < K) {
// 窗口右边界扩，如果不越界把扩之后的那个位置的值加到窗口累加值上
right++;
if (right == arr.length) {
break;
}
sum += arr[right];
} else {
sum -= arr[left++];
}
}
return len;
}
// for test
public static int right(int[] arr, int K) {
int max = 0;
for (int i = 0; i < arr.length; i++) {
for (int j = i; j < arr.length; j++) {
if (valid(arr, i, j, K)) {
max = Math.max(max, j - i + 1);
}
}
}
return max;
}
// for test
public static boolean valid(int[] arr, int L, int R, int K) {
int sum = 0;
for (int i = L; i <= R; i++) {
sum += arr[i];
}
return sum == K;
}
// for test
public static int[] generatePositiveArray(int size, int value) {
int[] ans = new int[size];
for (int i = 0; i != size; i++) {
ans[i] = (int) (Math.random() * value) + 1;
}
return ans;
}
// for test
public static void printArray(int[] arr) {
for (int i = 0; i != arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
int len = 50;
int value = 100;
int testTime = 500000;
System.out.println("test begin");
for (int i = 0; i < testTime; i++) {
int[] arr = generatePositiveArray(len, value);
int K = (int) (Math.random() * value) + 1;
int ans1 = getMaxLength(arr, K);
int ans2 = right(arr, K);
if (ans1 != ans2) {
System.out.println("Oops!");
printArray(arr);
System.out.println("K : " + K);
System.out.println(ans1);
System.out.println(ans2);
break;
}
}
System.out.println("test end");
}
}
```
### 1.1.2 第二连例题
有一个数组，值可以为正可以为负可以为0。给定一个值sum，求子数组中累加和等于sum的最大长度？
> 该题和第一连问题的区别是，数组的值可正可负可零，单调性消失了。对于数组问题，我们常见的解决子数组的思考思路，如果以每一个位置开头能求出一个答案，那么目标答案一定在其中。反过来如果以每一个位置为结尾能求出一个答案，那么目标答案一定也在其中
> 该题思路用第二种比较方便，我们以某个位置i结尾，之前的数累加和等于目标sum，求该位置满足此条件的最长数组。该种思路等同于，从0位置开始到i位置的累加和（allSum），减去从0位置到最早和0位置的累加和等于allSum-sum的位置j。那么原问题的答案是j+1到j位置的长度。预置，0位置累加和位置等于-1位置
```Java
public class Code02_LongestSumSubArrayLength {
// arr数组，累加和为k的最长子数组返回
public static int maxLength(int[] arr, int k) {
if (arr == null || arr.length == 0) {
return 0;
}
// key表示累加和，value表示最早出现的位置
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
// 0位置的累加和，最早出现在-1位置。预置
map.put(0, -1); // important
// 最大长度是多少
int len = 0;
// 累加和多大
int sum = 0;
for (int i = 0; i < arr.length; i++) {
sum += arr[i];
if (map.containsKey(sum - k)) {
// j+1到i有多少个数，i-j个
len = Math.max(i - map.get(sum - k), len);
}
if (!map.containsKey(sum)) {
map.put(sum, i);
}
}
return len;
}
// for test
public static int right(int[] arr, int K) {
int max = 0;
for (int i = 0; i < arr.length; i++) {
for (int j = i; j < arr.length; j++) {
if (valid(arr, i, j, K)) {
max = Math.max(max, j - i + 1);
}
}
}
return max;
}
// for test
public static boolean valid(int[] arr, int L, int R, int K) {
int sum = 0;
for (int i = L; i <= R; i++) {
sum += arr[i];
}
return sum == K;
}
// for test
public static int[] generateRandomArray(int size, int value) {
int[] ans = new int[(int) (Math.random() * size) + 1];
for (int i = 0; i < ans.length; i++) {
ans[i] = (int) (Math.random() * value) - (int) (Math.random() * value);
}
return ans;
}
// for test
public static void printArray(int[] arr) {
for (int i = 0; i != arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
int len = 50;
int value = 100;
int testTime = 500000;
System.out.println("test begin");
for (int i = 0; i < testTime; i++) {
int[] arr = generateRandomArray(len, value);
int K = (int) (Math.random() * value) - (int) (Math.random() * value);
int ans1 = maxLength(arr, K);
int ans2 = right(arr, K);
if (ans1 != ans2) {
System.out.println("Oops!");
printArray(arr);
System.out.println("K : " + K);
System.out.println(ans1);
System.out.println(ans2);
break;
}
}
System.out.println("test end");
}
}
```
对于数组arr，可正可负可零。求子数组中1和2数值个数相等的子数组最长的长度，返回？
> 把数组中其他数值变为0，为1的数值仍为1，为2的数值变为-1。处理好之后，求子数组累加和为0的最长子数组。
> 很多数组问题，可以转化为求子数组累加和问题，需要训练敏感度
### 1.1.2 第三连例题
一个数组arr中，有正数，有负数，有0。给定累加和目标k，求所有子数组累加和中小于等于k的数组的最大长度？
概念定义：
以i开头的子数组中，所有可能性中，哪一个能让累加和最小的范围是什么？
例如[3,7,4,-6,6,3,-2,0,7-3,2],准备两个辅助数组minSum[],minEnd[]。minSum记录从i开始后续子数组中累加和最小的值。minEnd记录i开始后续子数组中累加和最小的累加和的终止位置j
对于i位置，如果有变为正数，那么我累加和最小的就是我自己；如果自身是正数，累加和最小就是我右侧位置计算出来的最小累加和
如此操作，任意i位置，最小子数组累加和我们能拿到，最小累加和子数组的右边界我们能拿到
> 该题巧妙之处是排除可能性，比较难
```Java
public class Code03_LongestLessSumSubArrayLength {
public static int maxLengthAwesome(int[] arr, int k) {
if (arr == null || arr.length == 0) {
return 0;
}
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--) {
if (minSums[i + 1] < 0) {
minSums[i] = arr[i] + minSums[i + 1];
minSumEnds[i] = minSumEnds[i + 1];
} else {
minSums[i] = arr[i];
minSumEnds[i] = i;
}
}
int end = 0;
int sum = 0;
int res = 0;
// i是窗口的最左的位置，end扩出来的最右有效块儿的最后一个位置的，再下一个位置
// end也是下一块儿的开始位置
// 窗口：[i~end)
for (int i = 0; i < arr.length; i++) {
// while循环结束之后：
// 1) 如果以i开头的情况下，累加和<=k的最长子数组是arr[i..end-1]，看看这个子数组长度能不能更新res；
// 2) 如果以i开头的情况下，累加和<=k的最长子数组比arr[i..end-1]短，更新还是不更新res都不会影响最终结果；
while (end < arr.length && sum + minSums[end] <= k) {
sum += minSums[end];
end = minSumEnds[end] + 1;
}
res = Math.max(res, end - i);
if (end > i) { // 窗口内还有数 [i~end) [4,4)
sum -= arr[i];
} else { // 窗口内已经没有数了，说明从i开头的所有子数组累加和都不可能<=k
end = i + 1;
}
}
return res;
}
public static int maxLength(int[] arr, int k) {
int[] h = new int[arr.length + 1];
int sum = 0;
h[0] = sum;
for (int i = 0; i != arr.length; i++) {
sum += arr[i];
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];
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;
if (arr[mid] >= num) {
res = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
return res;
}
// for test
public static int[] generateRandomArray(int len, int maxValue) {
int[] res = new int[len];
for (int i = 0; i != res.length; i++) {
res[i] = (int) (Math.random() * maxValue) - (maxValue / 3);
}
return res;
}
public static void main(String[] args) {
System.out.println("test begin");
for (int i = 0; i < 10000000; i++) {
int[] arr = generateRandomArray(10, 20);
int k = (int) (Math.random() * 20) - 5;
if (maxLengthAwesome(arr, k) != maxLength(arr, k)) {
System.out.println("Oops!");
}
}
System.out.println("test finish");
}
}
```
- 第一节 复杂度、排序、二分、异或
- 第二节 链表、栈、队列、递归、哈希表、顺序表
- 第三节 归并排序、随机快排介绍
- 第四节 比较器与堆
- 第五节 前缀树、桶排序以及排序总结
- 第六节 链表相关面试题总结
- 第七节 二叉树基本算法
- 第八节 二叉树的递归思维建立
- 第九节 贪心算法深度剖析
- 第十节 并查集、图相关算法介绍
- 第十一节 暴力递归思维、动态规划思维建立
- 第十二节 用简单暴力递归思维推导动态规划思维
- 第十三节 单调栈和窗口及其更新结构
- 第十四节 类似斐波那契数列的递归
- 第十五节 认识KMP算法与bfprt算法
- 第十六节 认识Manacher(马拉车)算法
- 第十七节 认识Morris遍历
- 第十八节 线段树
- 第十九节 打表技巧和矩阵处理技巧
- 第二十节 组累加和问题整理
- 第二十一节 哈希函数有关的结构和岛问题
- 第二十二节 解决资源限制类题目
- 第二十三节 有序表原理及扩展
- 第二十四节 AC自动机和卡特兰数
- 第二十五节 算法面试专题-链表
- 第二十六节 算法面试专题-二叉树
- 第二十七节 算法面试专题-字符串