LeetCode 560. Subarray Sum Equals K

时间:2022-01-29 16:18:31
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的可能