1457. Search Subarray

Given an array arr and a nonnegative integer k, you need to find a continuous array from this array so that the sum of this array is k. Output the length of this array. If there are multiple such substrings, the return end position is the smallest, and if there are more than one, the return start position is the smallest. If no such subarray is found, -1 is returned.

The length of the array does not exceed $10^6$, each number in the array is less than or equal to $10^6$, and kdoes not exceed $10^6$.

Have you met this question in a real interview?  

Example

Example 1 :

Input：arr=[1,2,3,4,5] ，k=5
Output：2
Explanation:
In this array, the earliest contiguous substring is [2,3].

Example 2 :

Input：arr=[3,5,7,10,2] ，k=12
Output：2
Explanation:
In this array, the earliest consecutive concatenated substrings with a sum of 12 are [5,7].

class Solution { public: /** * @param arr: The array * @param k: the sum * @return: The length of the array */ int searchSubarray(vector<int> &arr, int k) { // Write your code here const int size = arr.size(); if(size == 0){ return -1; } unordered_map<int, int> toPos; toPos[0] = -1; int sum = 0; for(int i = 0; i < size; i++){ sum += arr[i]; if(toPos.find(sum - k) != toPos.end()){ return i - toPos[sum - k]; } if(toPos.find(sum) == toPos.end()){ toPos[sum] = i; } } return -1; } };