leetcode-day-22

LeetCode 30 days Challenge - Day 22

本系列将对LeetCode新推出的30天算法挑战进行总结记录，旨在记录学习成果、方便未来查阅，同时望为广大网友提供帮助。

---

Subarray Sum Equals K

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

Example 1:

Input:nums = [1,1,1], k = 2
Output: 2

Note:

1. The length of the array is in range [1, 20,000].
2. The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

---

Solution

题目要求分析：给定一个整型数组、一个整数k，求数组中所有和为k的子数组个数。

解法：

本题暴力解法、求累计值再遍历的O(n^2^)解法较简单，可以参考原题讨论区，本文主要就介绍O(n)的做法。

首先考虑该式：前 i 项和 - 前 j 项和 = i 到 j 的和（i > j）；实际任务即：找到所有满足i 到 j 的和等于k的子数组。

根据该思想，在遍历数组nums的过程中，假设当前位置为i，执行nums[i] += nums[i-1]，迭代来看，nums[i]即为前 i 项和。根据等式性质，只要检测nums[i] - k（即nums[j]）是否在之前出现过，就能确定是否存在子数组。

我们使用一个哈希结构来存储 前 i 项和出现的次数，这样就能在一次遍历的过程中，O(1)时间找到答案。

具体操作如下：

1. 进入循环，遍历nums；
2. 当累加后，如果当前值为k，说明从0到该位置的子数组满足条件，结果加1；
3. 在哈希表中查找 nums[i] - k：m.find(nums[i] - k) != m.end()，unordered_map的find方法，当键不存在时，返回位置end()；
4. 将当前nums[i]的值存入哈希表中，若已存在则加1：m[key]保存key出现的次数。

---

int subarraySum(vector<int>& nums, int k) {
    int res = 0;
    unordered_map<int, int> m;
    for (int i = 0; i < nums.size(); i++) {
        if (i > 0) nums[i] += nums[i-1];
        res += nums[i] == k;
        if (m.find(nums[i] - k) != m.end()) res += m[nums[i] - k];
        m[nums[i]]++;
    }
    return res;
}

---

传送门：Subarray Sum Equals K

Karl