[LeetCode 560. 和为K的子数组] | 刷题打卡

题目描述

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

示例

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

说明

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

思路

提示：所有的算法题拿到题目一定要仔细审题，往往其貌不扬的几句话中可以暗藏不少玄机。这道题几个关键信息就是：

1. 整数数组，即数组元素可能包括 正整数 ， 负整数 和 0
2. 要求找出 连续的 子数组

拿到这个题目，最容易想到的就是暴力解决法。相信第一反应去遍历的不止我一个。先贴一下暴力代码：

var subarraySum = function(nums, k) {
    let res = 0;
    for (let i = 0; i < nums.length; i++) {
        const element = nums[i];   
        if (element === k) {
            res++;
        }
        let p = i + 1;
        let initValue = element;
        while (p < nums.length) {
            initValue += nums[p]
            p++
            if (initValue === k) {
                res++
            }
        }
    }
    return res;
}

一顿操作猛如虎后，信心满满的提交代码，却发现虽然通过了所有的测试用例，但是超出时间限制了。

分析下上面的代码不难发现，暴力遍历法的时间复杂度是O(n^2)。因为我们针对每个元素，都要对该索引后面的元素再进行一次遍历求和。这种解法在数组元素少的时候是可以的，但是一旦数据大起来，消耗的时间将按指数倍上升。再仔细审题，题目说明中明确给出数组的长度是 [1, 20,000]。显然，该题目的本意并不是让你给出暴力解决方案。小伙伴们面试的时候也要注意了，不要放过每一句说明信息。不然你信心满满的答案却是面试官心中并不期许的答案。

那么要怎么样优化呢？和数组求和有关的题目，很自然就会想到哈希表。哈希表是减少遍历次数的有效手段。

先贴代码:

var subarraySum = function(nums, k) {
    const mp = new Map();
    mp.set(0, 1);
    let count = 0, pre = 0;
    for (const x of nums) {
        pre += x;
        if (mp.has(pre - k)) {
            count += mp.get(pre - k);
        }
        if (mp.has(pre)) {
            mp.set(pre, mp.get(pre) + 1);
        } else {
            mp.set(pre, 1);
        }
    }
    return count;
}

代码中的map存的是前缀和满足改前缀和的次数。count是满足的连续子数组的个数。每次遍历，更新前缀和，如果前缀和减去目标和出现在map中，count则加上满足的次数。

其理论推导为：

定义pre[i]为[0...i]里所有数的和，则pre[i]可以由pre[i-1]递推而来，即：pre[i] = pre[i-1] + nums[i],那么[j...i]这个子数组和为k这个条件可以转化为 pre[i] - pre[j-1] === k,移项之后可的符合条件的下标需要满足pre[j-1]=pre[i]-k.

复杂度分析

时间复杂度：O(n)，其中n为数组的长度。我们遍历数组的时间复杂度为 O(n)，中间利用哈希表查询删除的复杂度均为 O(1)，因此总时间复杂度为 O(n)。

空间复杂度：O(n)，其中n为数组的长度。哈希表在最坏情况下可能有n个不同的键值，因此需要O(n)的空间复杂度。

总结：

要擅长利用数据结构，如本题中的哈希表 进行算法优化。所以说 算法与数据结构 是密不可分的。不要一上来就刷题，对数据结构没有细致的了解很难灵活运用。算法不能一蹴而就，只能细水长流。一起加油??

下个题目见~

本文正在参与「掘金 2021 春招闯关活动」, 点击查看 活动详情：juejin.cn/post/693314…