最后更新
二刷
木有头绪啊。。
看答案明白了。
用的是two sum的思路。
比如最终找到一个区间，[i,j]满足sum = k，这个去见可以看做是
[0,j]的sum 减去 [0,i]的Sum.
维护一个map，来记录0-i的和，我们希望
0~i + k = 0 ~ j ，这样就可以更新一次i~j的区间长度作为候补的结果。
Time: O(n)
Space: O(n)
public class Solution {
public int maxSubArrayLen(int[] nums, int k) {
if (nums.length == 0) return 0;
Map<Integer,Integer> map = new HashMap<>();
int sum = 0;
int res = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
if (sum == k) {
res = Math.max(res, i + 1);
} else if (map.containsKey(sum - k)) {
res = Math.max(res, i - map.get(sum - k));
}
if (!map.containsKey(sum)) {
map.put(sum, i);
}
}
return res;
}
}
一刷
今晚各种卡。看提示是MAP，有了头绪。
先计算从0-0 0-1 0-2 0-3 0-4 0-n的值，累加就行，存入map，注意key是累加的值，value是0-index的indx。那么可能会有重复穿线的值，比如0-4 0-8的累加结果都是6，我们取最后的，一会解释。。
构建完MAP之后查MAP，看看有没有哪个值是target，有就更新一下结果= map.get(k) - 0，-0因为当前所有值都是从0开始累加的。
然后遍历数组。
看看1-1 1-2 1-3 1-5 .. 1-n有没有值等于target + nums[0]，有就更新
再2-2 2-3 2-4 2-5 ... 2-n == target + nums[0] + nums[1]。。有就更新
解释一开始说的，为什么选后出现的INDEX作为value.
是因为我们倾向于选择晚出现的，因为如果1个值被查到，长度是返还的INDEX-当前的I，肯定是INDEX越大越符合我们要求，所以INDEX取晚出现的。
刚才讲过程的时候发现问题了。。好像没必要遍历两次，第二次查表的时候需要查的值越来越少，0-n 1-n 2-n，虽然查表都是O(1)不影响，但是似乎一遍就能下来。
假如结果是 1-5 减去1-3，在一开始建表的时候就可以计算，而且他的结果不会被后面的计算影响。 而6-8的结果只会从1-8 - 1-6得到，或者先从这个地方得到，不存在以后又遇到，就算以后又出现，肯定是1-8返还的index减去第一次出现的1-6得到的结果最大。。
好像可以，二刷再说。。先放个2 PASS的，反正都是O(N)
public class Solution
{
public int maxSubArrayLen(int[] nums, int k)
{
Map<Integer,Integer> map = new HashMap<Integer,Integer>();
int sum = 0;
for(int i = 0; i < nums.length;i++)
{
sum += nums[i];
map.put(sum,i);
}
int res = 0;
if(map.containsKey(k))
res = map.get(k)+1;
for(int i = 0; i < nums.length;i++)
{
if(map.containsKey(k+nums[i]))
res = Math.max(res,map.get(k+nums[i]) - i);
k += nums[i];
}
return res;
}
}