[leetcode] 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].

分析：题目翻译一下：给定一个数组，要求找连续子数组之和为k的这样的子数组的个数。

第一个思路：首先想到用滑动窗口来做，保存两个指针，一个是left，一个right，sum保存着从left--right的值。如果sum比k小，那么就需要扩大窗口，right右移（注意这里可能会到达最右端的判断）；如果sum==k，满足条件，窗口缩小，left右移；如果sum>k，窗口缩小，left右移。

整理代码如下：

 1 public int subarraySum(int[] nums, int k) {
 2         int left = 0;
 3         int right = 0;
 4         int sum = nums[0];
 5         int count = 0;
 6         while ( right < nums.length  && left < nums.length ){
 7             System.out.println(sum);
 8             if ( sum < k ){
 9                 if ( right == nums.length - 1 ){
10                     sum += nums[right];
11                     right++;
12                 }else if ( right < nums.length - 1){
13                     right ++;
14                     sum += nums[right];
15                 }else {
16                     break;
17                 }
18                 continue;
19             }else if ( sum == k ){
20                 count ++;
21                 sum -= nums[left];
22                 left++;
23                 continue;
24             }else if ( sum > k ){
25                 sum -= nums[left];
26                 left++;
27             }
28         }
29         return count;
30     }

用全部正整数的数组调试了一下发现是对的。但是！没有办法满足负数和正数并存的情况，比如[-1,-1,1]，这种就没有办法了。所以要寻找更好的方法。

思路2：这个题目，用传统的思路想，肯定是要计算sum(i,j)，然后计算左右的任意两个位置和之后，进行比较。显然这种时间复杂度是O(n^2)。

这里我们注意到，sum(i,j)=sum(0,j)-sum(0,i-1),所以如果我们用一个map保存（0，each i in nums.lenght），也就是sum(0,i-1)，那么时间复杂度可以降低为O（n）了。

代码如下：

 1 class Solution {
 2     public int subarraySum(int[] nums, int k) {
 3         Map<Integer,Integer> map = new HashMap<>(); //记录sum，frequency
 4         int sum = 0;
 5         int result = 0;
 6         map.put(0,1);
 7         for ( int i = 0 ; i < nums.length ; i ++ ){
 8             sum += nums[i];
 9             if ( map.containsKey(sum - k) ){
10                 result += map.get(sum-k);
11             }
12             map.put(sum,map.getOrDefault(sum,0)+1);
13         }
14         return result;
15     }
16 }

[leetcode] Subarray Sum Equals K

相关推荐