560.和为K的子数组

560. 和为K的子数组

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

示例 1 :

输入:nums = [1,1,1], k = 2 输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。说明 :

数组的长度为 [1, 20,000]。数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/subarray-sum-equals-k 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

思路一：

暴力法

两层循环
从头开始遍历，i表示子数组的开始位置，j表示子数组的结束位置
当和为 K时，count ++
最终返回 result
时间复杂度 : O(N ^ 2) ，其中N为数组的长度
空间复杂度 : O(1)
提交后，算法通过了。但是用时长，算法设计复杂度高

代码如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


    public int subarraySum(int[] nums, int k) {

        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            if (num == k) count++;

            for (int j = i + 1; j < nums.length; j++) {
                num += nums[j];
                if (num == k) {
                    count ++;
                }
            }
        }
        return count;
    }

屏幕快照 2020-05-27 上午11.02.19

思路二：

利用前序和，哈希表优化

前序和，是指从数组第0项，到数组当前项的总和
如果用数组 prefixsum 表示
prefixsum[i] 为数组第0项，到数组第 i 项的总和
所以 nums 第 i 项到第 j 项的总和为 prefixsum[j] - prefixsum[i - 1]
题目等价交换
有几种i, j组合，使得 nums[i] 累加到 nums[j] 的总和为 k
有几种i, j组合，使得 prefixsum[j] - prefixsum[i -1] == k
引入哈希表
哈希表中存放 <前序和：出现次数>
当遍历到数组某一位置时，如果其前序和与 K的差值，在哈希表中存在
则次数 += map.get(前序和 - 差值)
map中赋值当前前序和，如果之前有，则+1, 没有则赋值1
时间复杂度 O(N)
空间复杂度 O(N)

代码如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


public static int subarraySum1(int[] nums, int k) {

        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0,1);
        int count = 0, prev = 0;
        for (int i = 0; i < nums.length; i++) {
            prev += nums[i];
            if (map.containsKey(prev - k))
                count += map.get(prev - k);
            map.put(prev,map.getOrDefault(prev, 0) + 1);
        }
        return count;
    }

屏幕快照 2020-05-27 下午1.11.51

Contents

560. 和为K的子数组

题解：

思路一：

思路二：