560. 和为K的子数组

Chenyi_li / 2023-08-13 / 原文

1.暴力法的优化

子循环中记录和

class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0;
        for(int i=0; i<nums.length; i++){
            int sum=0;
            for(int j=i;j<nums.length;j++){
                sum+=nums[j];

                if(sum==k)  count++;
            }
        }

        return count;

    }

}

2.前缀和

class Solution {
    public int subarraySum(int[] nums, int k) {
         // key：前缀和，value：key 对应的前缀和的个数
        Map<Integer, Integer> map = new HashMap<>();

        map.put(0, 1);
        int preSum = 0;
        int count = 0;
        for (int num : nums) {
            preSum += num;

            if (map.containsKey(preSum - k)) {
                count += map.get(preSum - k);
            }

            map.put(preSum,map.getOrDefault(preSum,0)+1);
        }
        return count;
    }
}


// -1是索引，等号右边的0是前缀和，代表你还没遍历数组时，就已经出现一次前缀和等于0的情况。如果不加，会漏掉一种prefixSum[i]本身就等于k的情况。

作者：笨猪爆破组
链接：https://leetcode.cn/problems/subarray-sum-equals-k/solutions/247991/dai-ni-da-tong-qian-zhui-he-cong-zui-ben-fang-fa-y/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。