数组累加和——汇总
package ArraySum
import (
"testing"
)
//数组累加和问题三连
/*
arr[] 正数 sum
累加和为K 的子数组最大长度
子数组一定是连续的
*/
/*
此题因为数组中只包含正数，所以，数组的长度和累加和可以建立起单调性，数组长度越大，那么累加和也就越大。
窗口从左向右滑动
1.如果窗口内值的累加和等于给定的K,即找到了一种答案，用该答案与旧的答案比较，取其大者，
同时数组累加和减去窗口内第一个数，窗口左边界右移，另其出窗口。此时窗口内值的累加和一定小于K
2.如果窗口内值的累加和小于给定的K,那么让窗口右边界右移，若下标已经越界，则直接结束循环，反之则让新的数据进入窗口，
同时窗口内值的累加和加上新进来的数
3.如果窗口内值的累加和大于给定的K，那么窗口内值的累加和减去数窗口内第一个数，窗口的左边界右移，令窗口的第一个数出窗口
*/
// 滑动窗口
func getMaxLength(arr []int, K int) int {
if arr == nil || len(arr) == 0 || K < 0 {
return 0
}
left, right := 0, 0 //窗口 [L,R] [0,0]
sum := arr[0]
length := 0
for right < len(arr) {
if sum == K {
length = Max(length, right-left+1) // R - L + 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
}
func Max(a, b int) int {
if a < b {
return b
}
return a
}
func TestWindowsGetMaxLength(t *testing.T) {
arr := []int{1, 2, 3, 4, 5, 6}
t.Log(getMaxLength(arr, 6))
}
/*
arr[] 有正有负有0， 求sum == k的最长的子数组长度
两种方法
第一种，求以下标i开头的子数组累加和，sum == k
第二种，求以下标i结尾的子数组累加和，sum == k
遍历的过程中求出各个下标位置的代表的前缀和，放入map中 value：索引 key：到该索引位置的前缀和
我们以第二种方法为例，若索引i位置结束的前缀和 减去 索引j([0,i))位置的前缀和 刚好 等于 已经存在的某个累加和，
那么则认为出现了一种答案，用该答案与旧答案相比较，得到最优答案
*/
func maxLength(arr []int, k int) int {
if arr == nil || len(arr) == 0 {
return 0
}
mp := map[int]int{0: -1}
// 0:-1 该条数据非常重要，避免某一项累加和为0时，影响最大长度
// 如 [8, -8, 12], k = 12 的最大长度是3， 若 8 与 -8 相加，则等于0，该0出现的位置(index = 1)会影响到最终的长度计算
length := 0
sum := 0
for i := 0; i < len(arr); i++ {
sum += arr[i]
if value, ok := mp[sum-k]; ok {
length = Max(i-value, length)
}
if _, ok := mp[sum-k]; !ok {
mp[sum] = i
}
}
return length
}
func TestMaxLength(t *testing.T) {
arr := []int{1, 2, -1, 3, 9, 13, -8, 5}
t.Log(maxLength(arr, 5))
}
/*
有一个数组，有正有负有0,
如果它的子数组中含有1的数量和含有2的数量是一样多的，则认为这样的子数组是达标的，返回这样的子数组的最大的长度
[5, 6,8,9,1,0,2,3]
[0,0,0,0,1,0,-1,0]
遍历数组，既不是0也不是1 的数，让他变成0
是1的维持1不变
是2的变成-1
此时求累加和为0的最长子数组
1 和 2 的数量一样时，才会抵消
*/
/*
arr 有正负0 所有小于等于k 的子数组都达标， 问哪一个是小于等于k的最长的
最优解: O(N)
先定义一个概念：
以i开头的情况下，它后面所有可能性中，能让他的累加和最小的信息是什么
以i开头的子数组，所有的子数组中，哪一个可以达到子数组最小的情况
[3,7,4,-6,6,3,-2,0,7,-3,2]
minSums 辅助数组
[ ]
0,1,2,3,4,5,6,7,8,9,10
minSums[i]代表子数组必须以i开头，后边随意选，所有可能性中，哪一个子数组中能够取得最小的累加和
minSumEnds i位置开头，j位置结尾，所有可能性中最小的
[ ]
0,1,2,3,4,5,6,7,8,9,10
从右往左填
10位置开头 2
minSums [ 2 ]
0,1,2,3,4,5,6,7,8,9,10
minSumEnds [ 10 ] 10 ~ 10 范围上，10 做右边界
0,1,2,3,4,5,6,7,8,9,10
--------------------------------------------
接下来是一个动态规划
9位置开头 -3
怎么得到最小的累加和
1. 只包含他自己的时候 9~9 -3
2. 不只包含自己，决定是否往右扩 Min( -3, -3 + 2 ) = - 3
minSums [ -3 2 ]
0,1,2,3,4,5,6,7,8,9,10
minSumEnds [ 9 10 ] 9 以自己做右边界
0,1,2,3,4,5,6,7,8,9,10
--------------------------------------------
8位置开头 7
怎么得到最小的累加和
1. 只包含他自己的时候 8~8 7
2. 不只包含自己，决定是否往右扩 Min( 7, 7 + -3 ) = 4
minSums [ 4 -3 2 ]
0,1,2,3,4,5,6,7,8, 9,10
minSumEnds [ 9 9 10 ]
0,1,2,3,4,5,6,7,8, 9,10
--------------------------------------------
7位置开头 0
怎么得到最小的累加和
1. 只包含他自己的时候 7~7 0
2. 不只包含自己，决定是否往右扩 Min( 0, 0 + 4 ) = 0
minSums [ 0 4 -3 2 ]
0,1,2,3,4,5,6,7,8, 9,10
minSumEnds [ 7 9 9 10 ]
0,1,2,3,4,5,6,7,8, 9,10
--------------------------------------------
6位置开头 -2 向不向右扩都行，因为右侧是0，假设要往右扩
怎么得到最小的累加和
1. 只包含他自己的时候 6~6 0
2. 不只包含自己，决定是否往右扩 Min( -2, -2 + 0 ) = -2
minSums [ -2 0 4 -3 2 ]
0,1,2,3,4,5, 6,7,8, 9,10
minSumEnds [ 7 7 9 9 10 ]
0,1,2,3,4,5, 6,7,8, 9,10
--------------------------------------------
6位置开头 -2 向不向右扩都行，因为右侧是0，假设要往右扩
怎么得到最小的累加和
1. 只包含他自己的时候 6~6 0
2. 不只包含自己，决定是否往右扩 Min( -2, -2 + 0 ) = -2
minSums [ -2 0 4 -3 2 ]
0,1,2,3,4,5, 6,7,8, 9,10
minSumEnds [ 7 7 9 9 10 ]
0,1,2,3,4,5, 6,7,8, 9,10
--------------------------------------------
minSums [ 1 -2 0 4 -3 2 ]
0,1,2,3,4,5, 6,7,8, 9,10
minSumEnds [ 7 7 7 9 9 10 ]
0,1,2,3,4,5, 6,7,8, 9,10
--------------------------------------------
minSums [ 1 -2 0 4 -3 2 ]
0,1,2,3,4,5, 6,7,8, 9,10
minSumEnds [ 7 7 7 9 9 10 ]
0,1,2,3,4,5, 6,7,8, 9,10
以此类推
这两个辅助数组，i 往后所有可能性中，最小累加和被我们捕获到了，而且我们知道它的右边界
假设以0开始 0 ~ 7 是以0扩充的最小累加和是 35 K = 30 则以0 开头的答案没有
假设以0开始 0 ~ 7 是以0扩充的最小累加和是 5 K = 30 则继续往右扩
8~13 是6 则 5 + 6 < 30 可以继续往右扩，直到超过K
精髓：
0 ~ 7 8 ~ 13 14 ~ 29 30 ~ 超过K
0 ~ 29 是答案，长度是30 假设K是100， 0 ~ 29 的累加和假设是90， 把30位置的数加进来就会超过K，不加就不超，那么
1 ~ 29 的累加和是 多少 90 - arr[0],不从头扩，假设区间是1 ~ 29 = 90 - arr[0] 看此时 30开头的区间，能不能进来
该算法用到了舍弃可能性的优化方式
*/
func maxLengthAwesome(arr []int, k int) int {
if arr == nil || len(arr) == 0 {
return 0
}
N := len(arr)
minSums := make([]int, N)
minSumEnds := make([]int, N)
minSums[N-1] = arr[N-1]
minSumEnds[N-1] = N - 1
for i := N - 2; i >= 0; i-- {
if minSums[i+1] <= 0 { // 向右扩，有利可图 < 0 或 <= 0 <= 0 是为了更加的向右
minSums[i] = arr[i] + minSums[i+1]
minSumEnds[i] = minSumEnds[i+1]
} else { // 向右扩，无利可图
minSums[i] = arr[i] // 保存自己
minSumEnds[i] = i // 以自己做右边界
}
}
// end: (i...)(...)(...)(end.. X 从end 开始往下扩扩不动了，他之前的是扩出来的，不会超
// sum: 窗口内累加和
// res: 最大长度
end, sum, res := 0, 0, 0
/*
i.................(sum) end
i 是窗口的最左的位置，end扩出来的最右有效块儿的最后一个位置的，再下一个位置
end 也是下一块儿的开始位置
窗口：[ 1 ~ end )
*/
for i := 0; i < len(arr); i++ { // i... 开始扩的位置
// for 循环结束后
// 1. 如果以i开头的情况下,累加和<=k的最长子数组是arr[i...end-1],看看这个子数组
// 2. 如果以i开头的情况下,累加和<=k的最长子数比arr[i...end-1]短,更新还是不更新
for end < len(arr) && sum+minSums[end] <= k {
// (end....?)(?+1....
sum += minSums[end]
end = minSumEnds[end] + 1
}
// [i...](end....X)
// end 越界 i.......X
res = Max(res, end-i)
if end > i { // 窗口内还有数[i~end) [4,4)
sum -= arr[i]
} else { // 窗口内已经没有数了，说明以i开头的所有子数组累加和都不可能 <= k
end = i + 1
} // 有可能窗口弄没了，都不达标，所以要加上以上条件分支
}
return res
}