# 数组三连问题.

给定一个正整数组成的无序数组arr，给定一个正整数值K 找到arr的所有子数组里，哪个子数组的累加和等于K，并且是长度最大的返回其长度

主要技巧：利用单调性优化

都是正数的,来一个窗口就可以解决,因为他是有单调性的,

新来一个数,一定会让子数组的累加和变大,吐出去一个数一定会让累加和变小

给定一个整数组成的无序数组arr，值可能正、可能负、可能0 给定一个整数值K 找到arr的所有子数组里，哪个子数组的累加和等于K，并且是长度最大的返回其长度

主要技巧：利用预处理结构优化 + 讨论开头结尾 (大的子数组 - 小的子数组)

有负数了,那么就失去了单调性了,不能用窗口了.

子数组,我们老传统思想了,以i位置开头或结尾,最远推多远.

我们先对数组求一个累加和数组,则0~i位置的累加和sum我们很容易就能得到.假设100.

然后我们想求累加和为K的,例如k=30,那我们实际想求一个,有没有sum=70的,如果有,那我们累加和一减,不就是累加和=30的子数组吗.

如果没有,那我把当前累加和的位置存起来.

注意,建立位置Map的时候,先要把(0,-1)位置存进去.这样,才能对

例如[5,-5............],k=0,当遍历到0~1时候,我其实已经发现答案了,但是由于没有(0,-1)这个记录,我收集不到.

给定一个整数组成的无序数组arr，值可能正、可能负、可能0 给定一个整数值K 找到arr的所有子数组里，哪个子数组的累加和<=K，并且是长度最大的返回其长度

主要技巧：假设答案法+淘汰可能性（很难，以后还会见到）

这个题需要用到2个辅助结构.

和原答案一样长的两个子数组

minSums[],他记录的是,从i位置往后推,最小子数组sum值数组,他是倒着推出来的,从右往左,是否要包含右边的进来,还是只包含自己的一个动态规划

minSumEnds[],他和上面的辅助数组是一对儿,相辅相成的,他记录的是,上面得到了一个最小值之后,最右位置是多少.

例如 minSums[5] = 32,minSumEnds[5] = 7,代表5~7位置的累加和sum=32.

如果是minSums[12] = -5,minSumEnds[12] = 12,代表12位置自己组成的累加和sum=-5,他不往右扩是最好的.

这俩干嘛用????

我求累加和<=K的最长子数组,

我从0开始,看看最远推多远.

假设,我的辅助数组告诉我,0~3 = 4,4~6 = 3,7~10 = 5,k=10.

那我发现第一个最小子数组0~3的sum<=k 10,所以我把下一个最小子数组吸收进来,发现0~6 的sum = 7<= k 10,我继续吸收右面的子数组,,如果还能吸收,则吸收进来,如果不行了!!!我左侧往出退数,然后看能不能吸收进来新的子数组sum,

例如0~7,满足,但是发现8吸收进来就超了,吐出去0,看看0~7 的sum-arr[0] + minSums[8]能不能行,如果不行,反正它不影响我正确答案,只考虑他能不能吸收进来,推高可能性.

整个数组不回退的.