2017-12-19 19:11:57 +0000   |     algorithm leetcode array map   |   Viewed times   |    

题目

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:

朴素预求和,

先把到每一位为止的总和预先算出来,比如我有[1,1,1,1,1],预求和的结果就是[1,2,3,4,5]。我要求[2,4]区间的和,只需要做一次减法sum[4] - sum[2-1]

代码

class Solution {
    public int subarraySum(int[] nums, int k) {
        for (int i = 1; i < nums.length; i++) {
            nums[i] = nums[i-1] + nums[i];
        }
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i; j < nums.length; j++) {
                int sum = nums[j] - ((i == 0)? 0 : nums[i-1]);
                if (sum == k) { count++; }
            }
        }
        return count;
    }
}

结果

subarray-sum-equals-k-1

用一个Map储存预求和的结果,

用一个Map把每一位为止的预求和的结果出现的频率统计在一个HashMap里。

然后只需要遍历数组一次,复杂度是

代码

class Solution {
    public int subarraySum(int[] nums, int k) {
        int res = 0;
        int sum = 0;
        Map<Integer,Integer> map = new HashMap<>();
        map.put(0,1);
        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;
    }
}

结果

subarray-sum-equals-k-2