【大战蓝桥杯】 算法·每日一题（详解+多解）-- day9

提示:
1 <= nums.length <= 2 * 104
-1000 <= nums[i] <= 1000
-107 <= k <= 107

	class Solution {
		public int subarraySum(int[] nums, int k) {
			int res = 0;
			int sum = 0;
			Map<Integer, Integer> sums = new HashMap<>(nums.length);
			for (int i = 0; i < nums.length; i++) {
				sum += nums[i];
				// 查找前缀和中是否存在一个 target, 使得 sum - target = k
				if (sum == k) {
					++res;
				}
				int target = sum - k;
				Integer count = sums.get(target);
				if (count != null) {
					res += count;
				}
				// 增加前缀和为 sum 的个数
				sums.merge(sum, 1, Integer::sum);
			}
			return res;
		}
	}

class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        int res = 0, sum = 0;
        map.put(0, 1);
        for (int num : nums) {
            sum += num;
            if (map.containsKey(sum-k)) res += map.get(sum-k);
            if (map.containsKey(sum)) map.put(sum, map.get(sum)+1);
            else map.put(sum, 1);
        }
        return res;
    }
}

//与上面一样，不过可能更优雅
class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        int res = 0, sum = 0;
        map.put(0, 1);
        for (int num : nums) {
            sum += num;
            res += map.getOrDefault(sum - k, 0);
            map.merge(sum, 1, Integer::sum);
        }
        return res;
    }
}