本文共 1675 字，大约阅读时间需要 5 分钟。

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再往后的数组就不算了，其实是要算的。这样的话brute force的时间复杂度就到了n²

但是感觉这道题只能枚举，不知如何优化

class Solution {
       public int subarraySum(int[] nums, int k) {
           if(nums == null || nums.length == 0) {
               return 0;        }        int res = 0;        for(int i = 0; i < nums.length; i++) {
               int sum = nums[i];            if(sum == k) {
                   res++;                //continue;            }            for(int j = i + 1; j < nums.length; j++) {
                   sum += nums[j];                if(sum == k) {
                       res++;                    //break;                }                if(sum == 0) {
                       //break;                }            }        }        return res;    }}

解答

jiuzhang solution: HashMap

很聪明的方法 用HashMap存前缀，两个前缀之差就等于两点之间的元素和

class Solution {
       public int subarraySum(int[] nums, int k) {
           Map
   
     mp = new HashMap
    
     ();        for (int i = 1; i < nums.length; ++i) {
               nums[i] += nums[i - 1];        }        int ans = 0, tmp = 0;        mp.put (0, 1);        for (int i = 0; i < nums.length; ++i) {
               if (mp.containsKey (nums[i] - k)) ans += mp.get (nums[i] - k);            tmp = mp.containsKey (nums[i]) ? mp.get (nums[i]) + 1 : 1;            mp.put (nums[i], tmp);        }        return ans;    }}
    
   

转载地址：http://tyqvb.baihongyu.com/