JZTXT

LeetCode —— 子串

发布时间 2023-07-12 21:45:12作者: archaique

560. 和为 K 的子数组（哈希表）

官方题解：https://leetcode.cn/problems/subarray-sum-equals-k/solution/he-wei-kde-zi-shu-zu-by-leetcode-solution/

假设 left 到 right 下标的子数组和为 k
nums[left...right] = k
preSum[right] - preSum[left] = k
preSum[left] = preSum[right] - k
所以每次到 right 的时候，找到等于 preSum[right] - k 的 preSum[left] 有多少个
用一个 map 来记录，前缀和的 count （见官方题解动画）
key: 前缀和的值  
value: 前缀和为这个值的个数
map 要放入一个初始值 {0,1}

 

class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> leftPreSum2CntMap = new HashMap();
        
        leftPreSum2CntMap.put(0, 1);
        int rightPreSum = 0;
        // 总的满足条件的子数组个数的计数,最后的结果
        int count = 0;
        for (int right=0;right<nums.length;right++) {
            rightPreSum += nums[right];
            // [...i]
            // left 到 right 的子数组和为 k
            // nums[left...right] = k
            // preSum[right] - preSum[left] = k
            // preSum[left] = preSum[right] - k
            // 所以每次到 right 的时候，找到等于 preSum[right] - k 的 preSum[left] 有多少个
            Integer leftPreSumCnt = leftPreSum2CntMap.get(rightPreSum - k);
            if (leftPreSumCnt != null) {
                count += leftPreSumCnt;
            }

            // 将这次的和放到 map 里
            Integer rightPreSumCnt = leftPreSum2CntMap.get(rightPreSum);
            if (rightPreSumCnt == null) {
                rightPreSumCnt = 0;
            }
            leftPreSum2CntMap.put(rightPreSum, ++rightPreSumCnt);
        }
        return count;
    }
}