Given an array of integers and an integer k, you need to find the number of contiguous subarrays of that array and k.

Example 1: Input :nums = [1,1,1], k = 2 Output: 2, [1,1] and [1,1] are two different cases.Copy the code
In order to solve the time complexity problem, the first layer of start is used as the end of the target array. Time complexity O(N2)Copy the code

Solution 1: brute force cracking

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>=0; end--){ sum+=nums[end]; if(sum==k){ count++; } } } return count; }}Copy the code

Solution 2: Hashmap assisted solution

public class Solution { public int subarraySum(int[] nums, int k) { int count = 0, pre = 0; HashMap < Integer, Integer > mp = new HashMap < > (); mp.put(0, 1); for (int i = 0; i < nums.length; i++) { pre += nums[i]; if (mp.containsKey(pre - k)) { count += mp.get(pre - k); } mp.put(pre, mp.getOrDefault(pre, 0) + 1); } return count; }}Copy the code