Abstract: Prefix and hash table problems have been very around, feel said not too clear, recently will share some similar problems, help you consolidate the prefix and hash table problems solution ideas.

Unfinished points:

  • Give specific examples;

  • Why don’t you use “slide window” because you have negative numbers.

Answer key | “power button” 560: and subarray for K (medium)

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

Example 1:

Input :nums = [1,1,1], k = 2 output: 2, [1,1] and [1,1] are two different cases.Copy the code

Example 2:

Input: nums = [1,2,3], k = 3
Output: 2
Copy the code

Data range:


  • 1 Or less n u m s . l e n g t h Or less 2 ∗ 1 0 4 1 \le nums.length \le 2 * 10^4

  • – 1000 Or less n u m s [ i ] Or less 1000 -1000 \le nums[i] \le 1000

  • – 1 0 7 Or less k Or less 1 0 7 -10^7 \le k \le 10^7

Method 1: Violent solution (timeout)

  • Enumerates all contiguous subarrays to determine whether the sum of contiguous subarrays is equal to KKK

Reference code 1:

public class Solution {

    public int subarraySum(int[] nums, int k) {
        int len = nums.length;
        int count = 0;
        for (int left = 0; left < len; left++) {
            for (int right = left; right < len; right++) {

                int sum = 0;
                for (int i = left; i <= right; i++) {
                    sum += nums[i];
                }
                if(sum == k) { count++; }}}returncount; }}Copy the code

Time complexity: O(N3)O(N^3)O(N3), where NNN is the length of the array.

Method 2: Calculate the interval sum by prefix sum

  • Build prefixes and arrays to quickly calculate interval sums;
  • Notice that when you calculate the sum of intervals, the subscripts are offset.

Reference code 3:

public class Solution {

    public int subarraySum(int[] nums, int k) {
        int len = nums.length;
        // Calculate prefixes and arrays
        int[] preSum = new int[len + 1];
        preSum[0] = 0;
        for (int i = 0; i < len; i++) {
            preSum[i + 1] = preSum[i] + nums[i];
        }

        int count = 0;
        for (int left = 0; left < len; left++) {
            for (int right = left; right < len; right++) {
                // Interval and [left..right], note the subscript offset
                if (preSum[right + 1] - preSum[left] == k) { count++; }}}returncount; }}Copy the code

Time complexity: O(N2)O(N^2)O(N2), where NNN is the length of the array.

Even if the prefix sum is computed, the enumeration interval sum requires O(N2)O(N^2)O(N2) time complexity. The optimal approach is to remember some information as you iterate.

Method three: prefix and + hash table

Since we only care about The Times, we don’t care about the specific solution, we can use a hash table to speed up the operation. Because the sum of the same prefixes is stored, instead of adding them one by one, the time complexity is reduced to O(N)O(N)O(N).

This idea is not easy to think of, you need to do more similar problems to develop feelings. Similar issues include:

  • 1. The sum of two numbers;
  • “Force buckle” 1248 problem: statistics “graceful subarray”;
  • 454: Add four numbers together II.

Reference code 4:

import java.util.HashMap;
import java.util.Map;

public class Solution {

    public int subarraySum(int[] nums, int k) {
        // Key: prefix sum, value: number of prefix sum corresponding to key
        Map<Integer, Integer> preSumFreq = new HashMap<>();
        // For elements with subscript 0, the prefix sum is 0 and the number is 1
        preSumFreq.put(0.1);

        int preSum = 0;
        int count = 0;
        for (int num : nums) {
            preSum += num;

            PreSum -k = preSum -k = preSum -k = preSum -k
            if (preSumFreq.containsKey(preSum - k)) {
                count += preSumFreq.get(preSum - k);
            }

            (" Presumptive Freq"
            preSumFreq.put(preSum, preSumFreq.getOrDefault(preSum, 0) + 1);
        }
        returncount; }}Copy the code

“(presumptive freq.put (0, 1))”; .

Think about what the algorithm means: After counting the prefix and sum of the current number, let’s look up how many prefix sums before the current number are equal to preSum minus k.

That’s because the number of intervals that preSum – (preSum minus k) == k is what we care about.

In the first case, “PRESUMptive” is that there are no elements before the index 0, so “Presumptive” is zero, so “Presumptive” is one, so “Presumptive” freq.put (0, 1); This is necessary and reasonable.

Time complexity: O(N)O(N)O(N), where NNN is the length of the array.