【leetcode】leetcode560.和为K的子数组的详细题解及代码

题目描述

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。 示例 1 : 输入:nums = [1,1,1], k = 2 输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。 说明 : 数组的长度为 [1, 20,000]。 数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。

通过代码

class Solution { public: int subarraySum(vector<int>& nums, int k) { map<int,int>cur; cur[0]=1; int ans=0; int sum=0; for(auto i:nums) { sum+=i; ans+=cur[sum-k]; cur[sum]++; } return ans; } };

解题思路

刚开始我自己写的代码是两层for循环做的，时间复杂度是$O(n^2)$，也是可以通过所有样例的。但是我想，这个题目的最佳解法肯定不是这样，自己也没想到更好的解法。看了网上复杂度最低的代码，刚开始一直没有理解它的思路。后来想着找个实际的例子，把整个过程走一遍，果然结合实际例子就特别好理解了。下面是我自己理解的时候在纸上画的。nums，sum，ans，cur都是对应代码中相应的变量。 其实这个题目只用了一层循环，O(n)就解决了问题，是因为它每次找的就是以当前层的i作为子数组的最后一个元素，可以有几个子数组可以满足和为k。然后一步步往后，直到nums的最后一个元素，其实每次计算当前循环层的时候，都用到了前面的cur这个map，这也是它可以用一层循环就解决的原因。 这个题目的思路比较新颖，我自己刚开始没有想到，所以记录一下。