这类subarray,continuous subarray的套路就是必须以每个位置结尾的情况下解subproblem
例: 必须以0位置结尾情况下的最长。。。 必须以1位置结尾的最长。。
用一个HashMap记录所有sum to k 第一次出现的index
比如HashMap<10, 5> 累加和为10 第一次出现在index5.
下图例子是假设要求k=300的subarray. 我们从array 头开始iterate。当我们第一次碰到sum =200时候, 往HashMap里记录一下 Map<200, index>. 那么我们知道从index+1, 到end of array 这一段subarray 的sum肯定是100.
所以是我们把整个array 走一遍,一边走一边update HashMap. 把所有sum 的第一次出现的end index记下来。
然后如果当前的sum 减去 target K 的值 在map里有。 代表之前的某一个点我们曾经达到过这个sum-k的值。也就是从那个点到当前点的length 就是一个潜在的可能为最大的len. 然后我们拿去跟全局的max len比较一下。
Repeating Repeating 直到 走完整个array.