public int subarraySum(int[] nums, int k) { HashMap<Integer, Integer> sumMap = new HashMap<>(); //<每个下标的sum, sum出现次数> int sum = 0, res = 0; sumMap.put(0, 1); //sum刚好等于k for(int i = 0; i < nums.length; i++) { sum += nums[i]; if(sumMap.containsKey(sum - k)) { //sum[i] - sum[j] = k, 现在的sum减过去的sum刚好等于k, 即j到i这么长就是连续子数组的长度 res += sumMap.get(sum - k); } sumMap.put(sum, sumMap.getOrDefault(sum, 0) + 1); } return res; }
用map记录每次累加到下标 i 时的sum的次数,这个次数相当于有多种累加等于k的可能