20-《进阶》数组累加和问题.md

[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，此时的窗口大小就是一个满足条件的子数组大小，决定是否要更新答案；

```Go
package main

import (
	"fmt"
	"math"
)

// getMaxLength 有一个全是正数的数组，和一个正数sum。求该数组的累加和等于sum的子数组最长多长。 滑动窗口的表示
func getMaxLength(arr []int, K int) int {
	if len(arr) == 0 || K <= 0 {
		return 0
	}

	// 初始窗口位置[0,0],窗口当前只有第一个数
	left := 0
	right := 0
	sum := arr[0]
	length := 0

	for right < len(arr) {
		// 窗口的累加和sum等于我们的目标k。求窗口大小len
		if sum == K {
			length = int(math.Max(float64(length), float64(right - left + 1)))
			// 窗口累加和减去左窗口位置的值，左位置再出窗口
			sum -= arr[left]
			left++
		} else if sum < K {
			// 窗口右边界扩，如果不越界把扩之后的那个位置的值加到窗口累加值上
			right++
			if right == len(arr) {
				break
			}
			sum += arr[right]
		} else {
			sum -= arr[left]
			left++
		}
	}
	return length
}

// 最长的子数组为[1,1,1,1,1,1]返回长度6
func main() {
	arr := []int{3,2,1,1,1,6,1,1,1,1,1,1}
	sum := 6
	fmt.Println(getMaxLength(arr, sum))
}
```

### 1.1.2 第二连例题

有一个数组，值可以为正可以为负可以为0。给定一个值sum，求子数组中累加和等于sum的最大长度？

> 该题和第一连问题的区别是，数组的值可正可负可零，单调性消失了。对于数组问题，我们常见的解决子数组的思考思路，如果以每一个位置开头能求出一个答案，那么目标答案一定在其中。反过来如果以每一个位置为结尾能求出一个答案，那么目标答案一定也在其中

> 该题思路用第二种比较方便，我们以某个位置i结尾，之前的数累加和等于目标sum，求该位置满足此条件的最长数组。该种思路等同于，从0位置开始到i位置的累加和（allSum），减去从0位置到最早和0位置的累加和等于allSum-sum的位置j。那么原问题的答案是j+1到j位置的长度。预置，0位置累加和位置等于-1位置


```Go
package main

import "math"

// 有一个数组，值可以为正可以为负可以为0。给定一个值sum，求子数组中累加和等于sum的最大长度
// arr数组，累加和为k的最长子数组返回
func maxLength(arr []int, k int) int {
	if len(arr) == 0 {
		return 0
	}

	// key表示累加和，value表示最早出现的位置
	m := make(map[int]int, 0)
	// 0位置的累加和，最早出现在-1位置。预置
	m[0] = -1 // important
	// 最大长度是多少
	length := 0
	// 累加和多大
	sum := 0
	for i := 0; i < len(arr); i++ {
		sum += arr[i]
		if v1, ok := m[sum - k]; ok {
			// j+1到i有多少个数，i-j个
			length = int(math.Max(float64(i - v1), float64(length)))
		}
		if _, ok := m[sum]; !ok {
			m[sum] = i
		}
	}
	return length
}
```


对于数组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位置，最小子数组累加和我们能拿到，最小累加和子数组的右边界我们能拿到


> 该题巧妙之处是排除可能性，比较难


```Go
package main

import (
	"fmt"
	"math"
)

// 一个数组arr中，有正数，有负数，有0。给定累加和目标k，求所有子数组累加和中小于等于k的数组的最大长度
func maxLengthAwesome(arr []int, k int) int {
	if len(arr) == 0 {
		return 0
	}

	minSums := make([]int, len(arr))
	minSumEnds := make([]int, len(arr))
	minSums[len(arr) - 1] = arr[len(arr) - 1]
	minSumEnds[len(arr) - 1] = len(arr) - 1

	for i := len(arr) - 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
		}
	}

	end := 0
	sum := 0
	res := 0
	// i是窗口的最左的位置，end扩出来的最右有效块儿的最后一个位置的，再下一个位置
	// end也是下一块儿的开始位置
	// 窗口：[i~end)
	for i := 0; i < len(arr); i++ {
		// for循环结束之后：
		// 1) 如果以i开头的情况下，累加和<=k的最长子数组是arr[i..end-1]，看看这个子数组长度能不能更新res；
		// 2) 如果以i开头的情况下，累加和<=k的最长子数组比arr[i..end-1]短，更新还是不更新res都不会影响最终结果；
		for end < len(arr) && sum + minSums[end] <= k {
			sum += minSums[end]
			end = minSumEnds[end] + 1
		}
		res = int(math.Max(float64(res), float64(end - i)))
		if end > i { // 窗口内还有数 [i~end) [4,4)
			sum -= arr[i]
		} else { // 窗口内已经没有数了，说明从i开头的所有子数组累加和都不可能<=k
			end = i + 1
		}
	}
	return res
}

// 一个数组arr中，有正数，有负数，有0。给定累加和目标k，求所有子数组累加和中小于等于k的数组的最大长度; 暴力解法
func maxLength2(arr []int, k int) int {
	h := make([]int, len(arr) + 1)
	sum := 0
	h[0] = sum
	for i := 0; i != len(arr); i++ {
		sum += arr[i]
		h[i + 1] = int(math.Max(float64(sum), float64(h[i])))
	}
	sum = 0
	res := 0
	pre := 0
	length := 0
	for i := 0; i != len(arr); i++ {
		sum += arr[i]
		pre = getLessIndex(h, sum - k)
		if pre == -1 {
			length = 0
		} else {
			length = i - pre + 1
		}
		res = int(math.Max(float64(res), float64(length)))
	}
	return res
}

func getLessIndex(arr []int, num int) int {
	low := 0
	high := len(arr) - 1
	mid := 0
	res := -1
	for low <= high {
		mid = (low + high) / 2
		if arr[mid] >= num {
			res = mid
			high = mid - 1
		} else {
			low = mid + 1
		}
	}
	return res
}

//7
//7
func main() {
	arr := []int{3,7,4,-6,6,3,-2,0,7-3,2}
	k := 10
	fmt.Println(maxLength2(arr, k))
	fmt.Println(maxLengthAwesome(arr, k))
}
```