法一暴力搜索既然是子数组那就是连续的直觉是用滑动窗口。很容易写出来一个这样的解法因为我们先入为主了以为K和数组里的数都是正数可能后面还有0啊还有[2,-2,2,-2]或者[3,-2,-1]这样的那也好办让滑动窗口的右边界一直搜到数组最后就好了嘛。但是这个题是中等难度你这么做看起来像简单程度的。时间复杂度O(n^2)空间复杂度O1法二前缀和哈希PS别看前面的推导了直接跳到下面那张图就明白了。法一其实是暴力搜索接下来相当于是暴力搜索的优化嘛暴力搜索优化的思路就是利用之前的信息。想到了之前的《两数之和》只不过现在用“和”去代替其中一个数。比如目前遍历到nums[i]nums[i]是“一个数”nums[i]前面的所有可能前缀和下标从0到i-1从1到i-1,从2到i-1...就是“另一个数”。用和两数之和完全一样的思路去写的话两数之和是把nums[i]之前的所有数都存起来对应的我们把nums[i]之前的所有前缀和都存起来。稍微写了一下代码没跑通int totalCount0; //key放前缀和value放个数。因为前缀和可能会重复呀PS其实必须要走一遍暴力搜索并且遇到“邪恶的用例”才能意识到前缀和可能会重复进而才能定义出这里的value所以你根本无法一上来就想到法二破题那就用value记录前缀和为key的个数。 HashMapInteger,Integer map new HashMap(); for(int i0; ilen; i){ if(map.contains(k-nums[i])){ totalCounttotalCountmap.get(k-nums[i]); //保持和两数之和一样的思路 } //更新前缀和map里的所有元素key都更新为keynums[i] //发现时间复杂度依然是O(n^2)。 //而且要借助一个临时HashMap不然没法进行自更新 HashMapInteger,Integer tempMap new HashMap(); Iterator it map.iterator(); while(it.hasNext()){ Map.EntityInteger,Integer entity it.next(); //如果已经有了value1 if(tempMap.contains(entity.getKey()nums[i])){ tempMap.put(entity.getKey()nums[i]),tempMap.getValue()1); //如果没有value等于原map里的value }else{ tempMap.put(entity.getKey()nums[i],entity.getValue()); } } maptempMap; }我们会发现时间复杂度依然是O(n^2)而且本质上其实跟暴力搜索是一样的。。。但是起码思路方向是对的所以还要继续变通————所以存储的信息不能是nums[i]的所有前缀和下标从0到i-1从1到i-1,从2到i-1...我们内循环是在更新数据对吧我们不想要这层内循环那也就说明我们存储的信息得是不用更新的。那就是存[0,0],[0,1],[0,2]...[0,i-1]这样的前缀和。那怎么得到nums[i]的一系列前缀和呢做减法呀用[0,i-1]的前缀和减去[0,j]的前缀和不就是(j,i-1]的前缀和嘛。---》这就是代码里精髓部分if(map.containsKey(nowPre-k))的推导于是你就要想到除了map之外去存前面的前缀和以外还需要一个变量去维护当前的前缀和从nums[0]到nums[i]。class Solution { public int subarraySum(int[] nums, int k) { int len nums.length; int totalCount0; HashMapInteger,Integer map new HashMap(); //小精髓——用(0,1)去初始化 map.put(0,1); int nowPre 0; for(int i0; ilen; i){ //先更新前缀和 nowPre nowPrenums[i]; //整个算法的精髓就在这里 if(map.containsKey(nowPre-k)){ totalCounttotalCountmap.get(nowPre-k); } //如果前缀和之前不曾存在那么新增一个value1如果存在,value1 if(map.containsKey(nowPre)) map.put(nowPre,map.get(nowPre)1); else map.put(nowPre,1); } return totalCount; } }
