首页 > 代码库 > [leetcode 560. Subarray Sum Equals K]
[leetcode 560. 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:
- The length of the array is in range [1, 20,000].
- The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].
Subscribe to see which companies asked this question.
Show Tags
Show Similar Problems
笨方法就是遍历所有子序列，由于起点和终点都要遍历，所以时间复杂度是O（n^2）
本次的方法是遍历所有起点是最开始元素的子序列，我们起名叫sum[i]，只要两个sum[i]的差值是k，则两个i作为起点和终点的子序列就符合要求。由于起点就是最开始元素，只需遍历终点，时间复杂度为O（n）。
public class Solution {
public int subarraySum(int[] nums, int k) {
Map<Integer,Integer> map = new HashMap<Integer,Integer>();
map.put(0,1);
int sum = 0;
int res = 0;
for(int i = 0;i<nums.length;i++)
{
sum += nums[i];
res += map.getOrDefault(sum-k,0);
map.put(sum,map.getOrDefault(sum,0)+1);
}
return res;
}
}
[leetcode 560. Subarray Sum Equals K]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。