和为K的子数组

发表于 分类于 ， ， 阅读次数：

题目描述

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的连续子数组的个数 。

示例 1：

1
2
输入：nums = [1,1,1], k = 2
输出：2

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/subarray-sum-equals-k

我的题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int subarraySum(int[] nums, int k) {
        int sum=0;
        for(int i=0;i<nums.length;i++)
        {
            int j=i;
            int record=k;
            while(true)
            {
                if(j>nums.length-1)
                {
                    break;
                }
                record=record-nums[j];
                if(record==0)
                {
                    sum++;
                }
              
                j++;
            }
        }
        return sum;
    }
}

思路为先确定一个数，然后用和K依次减这个数后面的数，如果有零则记录，直到减到末尾，然后这个数向右移动，循环操作，找全部可能性，统计符合题意的个数。

大神题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import java.util.HashMap;
import java.util.Map;

public class Solution {

    public int subarraySum(int[] nums, int k) {
        // key：前缀和，value：key 对应的前缀和的个数
        Map<Integer, Integer> preSumFreq = new HashMap<>();
        // 对于下标为 0 的元素，前缀和为 0，个数为 1
        preSumFreq.put(0, 1);

        int preSum = 0;
        int count = 0;
        for (int num : nums) {
            preSum += num;

            // 先获得前缀和为 preSum - k 的个数，加到计数变量里
            if (preSumFreq.containsKey(preSum - k)) {
                count += preSumFreq.get(preSum - k);
            }

            // 然后维护 preSumFreq 的定义
            preSumFreq.put(preSum, preSumFreq.getOrDefault(preSum, 0) + 1);
        }
        return count;
    }
}

作者：liweiwei1419
链接：https://leetcode.cn/problems/subarray-sum-equals-k/solution/bao-li-jie-fa-qian-zhui-he-qian-zhui-he-you-hua-ja/

先看前缀和是什么

本地图片

由前缀和的思想就可以把问题转化为两数之差等于某个数的问题，这就回到了之前的经典题两数之和的方法了，用哈希表优化就可以，记得哈希表一开始放0和1，该题本身prefixSum可以不减任何其他的数组就是本身。