LeetCode560. Subarray Sum Equals K

it2022-05-05  144

我的方法:暴力。(结果:TLE。)

子数组的长度范围是1~n。这是最外层循环 i (0<i<length)。

对每一个长度,有一个开始,索引是 j (j+i<length)。

从 j 加到 j+i,又一个循环。

这是三重循环,我的。

class Solution { public: int subarraySum(vector<int>& nums, int k) { int sum=0; int res=0; for(int i=0;i<nums.size();i++){ for(int j=0;j+i<nums.size();j++){ for(int m=0;m<i+1;m++){ sum+=nums[j+m]; } if(sum==k) res++; sum=0; } } return res; } }; 我的三重循环

 


1. 另一种暴力:

 最外层是开始的索引。

第二层是结束的索引。(也可以看成是子数组长度)。

第三层是累加。

public class Solution { public int subarraySum(int[] nums, int k) { int count = 0; for (int start = 0; start < nums.length; start++) { for (int end = start + 1; end <= nums.length; end++) { int sum = 0; for (int i = start; i < end; i++) sum += nums[i]; if (sum == k) count++; } } return count; } } 官方暴力(java)

 


 

 2. 上面的暴力,第二层索引++,第三层又从头开始加。

其实2、3层可以合并成一个循环。

public class Solution { public int subarraySum(int[] nums, int k) { int count = 0; for (int start = 0; start < nums.length; start++) { int sum=0; for (int end = start; end < nums.length; end++) { sum+=nums[end]; if (sum == k) count++; } } return count; } } 官方两层循环(java,O(1)空间)

 


 

 

3. 累加和数组

借助一个sum数组。$\large sum[n]=\sum_{i=0}^{n-1}nums[i]$ ,其中sum[0]=0。

所以,子数组和nums[i:j]就是sum[j+1]-sum[i].

先一层循环,求出sum[]。

接下来一个两层循环,第一层是起始索引,第二层是结束。

 


 

4. 哈希

hashtable<sum , count>

一层循环,遍历到nums[i]时用sum-k,得到一个数。sum-k=tem , sum-tem=k. 

所以,还是累加和,不过不需要数组保存。用的是键值对。键是和,值是有多少个这样的和。(也可以看作有多少个索引,从开头加到这个索引,和为键)。查询为sum-k的键的值,就有多少个这样的索引,从这个索引到当前位置加起来和就为k‘,所以就有多少个子数组。

最开始要加个(0,1)进去,因为什么都还没加,和就是0。这个索引算作一个。

如果不加,那么sum=0时无法计数。

累加和数组法中sum[0]也是同样。

 

class Solution { public: int subarraySum(vector<int>& nums, int k) { int res = 0, sum = 0, n = nums.size(); unordered_map<int, int> m{{0, 1}}; for (int i = 0; i < n; ++i) { sum += nums[i]; res += m[sum - k]; ++m[sum]; } return res; } }; View Code

代码出自:http://www.cnblogs.com/grandyang/p/6810361.html

 代码有什么特殊的吗?有,才发现原来不需要判断key是否存在。不存在会返回0.


 

参考:

1. 官方题解

https://leetcode.com/problems/subarray-sum-equals-k/solution/

转载于:https://www.cnblogs.com/azureice/p/leetcode560.html


最新回复(0)