Abstract: Understand prefixes and hash table application techniques. If only prefixes and are used, enumerating interval lengths requires a quadratic level of time complexity. The method described in this topic can be traversed to remember some information during the traversal.

325. The sum is equal to the length of the smallest array of k

Given an array nums and a target value k, find the smallest array length whose sum is equal to k. If no subarray exists, 0 is returned.

Note:

The sum of numS arrays must be within the range of 32 – bit signed integers.

Example 1:

Input: nums = [1, -1, 5, -2, 3], k = 3 Output: 4 Explanation: The sum of subarrays [1, -1, 5, -2] is equal to 3 and has the longest length.Copy the code

Example 2:

Input: nums = [-2, -1, 2, 1], k = 1 Output: 2 Explanation: The sum of subarrays [-1, 2] is equal to 1 and has the longest length.Copy the code

Advanced: can you complete this problem in O(n) time?

Method 1: Calculate interval sum by prefix sum (timeout)

public class Solution {

    // Get interval sum from prefix sum: timeout

    public int maxSubArrayLen(int[] nums, int k) {
        int len = nums.length;
        int[] preSum = new int[len + 1];
        for (int i = 0; i < len; i++) {
            preSum[i + 1] = preSum[i] + nums[i];
        }

        int res = 0;
        for (int i = 0; i < len; i++) {
            for (int j = i; j < len; j++) {
                / / interval and
                int sum = preSum[j + 1] - preSum[i];
                if (sum == k) {
                    res = Math.max(res, j - i + 1); }}}returnres; }}Copy the code

Method two: prefix and hash table

Key words: continuous subarray, continuity is very important.

We find that we need to enumerate all the intervals by prefix sum (space for time), time complexity O(N2)O(N^2)O(N2).

Is it possible to go through it all at once? In fact, it can. Go ahead and do “space for time”, and remember the prefixes that you’ve walked through before as you figure out the sum. According to the

Prefix and _j + interval and k = prefix and _iCopy the code

Move the “interval sum k” from the left to the right to obtain:

Prefix and _j = prefix and _i - interval and kCopy the code

Therefore, when traversing a new number nums[I], we can calculate the preSum and preSum of the traversed elements, and then determine whether preSum -k is in the hash table.

And then I’m going to pair the keys

Key: preSum, value: ICopy the code

Store it in a hash table. Isn’t it the same idea as the sum of two numbers? The key points are in the code comments.

Attention (important)

Since we are looking for the “longest” continuous subarray, we only record the prefix and the first occurrence of the subscript.

Reference code:

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

public class Solution {

    public int maxSubArrayLen(int[] nums, int k) {
        int len = nums.length;
        Map<Integer, Integer> hashMap = new HashMap<>(len);
        // When calculating the length, we often add this sentinel
        hashMap.put(0, -1);

        int res = 0;
        int preSum = 0;
        for (int i = 0; i < len; i++) {
            preSum += nums[i];
            if (hashMap.containsKey(preSum - k)) {
                res = Math.max(res, i - hashMap.get(preSum - k));
            }

            // Note: since we are looking for the longest, only the first occurrence of the index is recorded
            if (!hashMap.containsKey(preSum)) {
                hashMap.put(preSum, i);
            }
        }
        returnres; }}Copy the code

Understand that subtraction between subscripts equals the length of the interval: