Problem

You are given a 0-indexed array nums and an integer target.

A 0-indexed array infinite_nums is generated by infinitely appending the elements of nums to itself.

Return _the length of theshortest subarray of the array _infinite_nums with a sum equal totarget . If there is no such subarray return -1.

Examples

Example 1

1
2
3
4
5

Input: nums = [1,2,3], target = 5
Output: 2
Explanation: In this example infinite_nums = [1,2,3,1,2,3,1,2,...].
The subarray in the range [1,2], has the sum equal to target = 5 and length = 2.
It can be proven that 2 is the shortest length of a subarray with sum equal to target = 5.

Example 2

1
2
3
4
5

Input: nums = [1,1,1,2,3], target = 4
Output: 2
Explanation: In this example infinite_nums = [1,1,1,2,3,1,1,1,2,3,1,1,...].
The subarray in the range [4,5], has the sum equal to target = 4 and length = 2.
It can be proven that 2 is the shortest length of a subarray with sum equal to target = 4.

Example 3

1
2
3
4

Input: nums = [2,4,6,8], target = 3
Output: -1
Explanation: In this example infinite_nums = [2,4,6,8,2,4,6,8,...].
It can be proven that there is no subarray with sum equal to target = 3.

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^5
  • 1 <= target <= 10^9

Solution

Method 1 – Sliding Window + Prefix Sums (Modulo)

Intuition

Since the array is repeated infinitely, we can simulate up to two rounds of nums (length up to 2n) to cover all possible subarrays. Use prefix sums and a hash map to find the shortest subarray with sum equal to target.

Approach

  1. Build prefix sums for up to 2n elements.
  2. For each prefix sum, check if (current_sum - target) exists in the map.
  3. Track the minimum length.
  4. If not found, return -1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

#include <unordered_map>
class Solution {
public:
    int minSizeSubarray(vector<int>& nums, int target) {
        int n = nums.size();
        long sum = 0;
        for (int x : nums) sum += x;
        int res = INT_MAX;
        vector<long> prefix(2*n+1, 0);
        for (int i = 0; i < 2*n; ++i) prefix[i+1] = prefix[i] + nums[i%n];
        unordered_map<long, int> mp;
        for (int i = 0; i <= 2*n; ++i) mp[prefix[i]] = i;
        for (int i = 0; i <= 2*n; ++i) {
            long need = prefix[i] - target;
            if (mp.count(need)) res = min(res, i - mp[need]);
        }
        if (target % sum == 0) return (target/sum)*n;
        return res == INT_MAX ? -1 : res;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

func minSizeSubarray(nums []int, target int) int {
    n := len(nums)
    sum := 0
    for _, x := range nums { sum += x }
    res := 1<<30
    prefix := make([]int, 2*n+1)
    for i := 0; i < 2*n; i++ { prefix[i+1] = prefix[i] + nums[i%n] }
    mp := map[int]int{}
    for i := 0; i <= 2*n; i++ { mp[prefix[i]] = i }
    for i := 0; i <= 2*n; i++ {
        need := prefix[i] - target
        if j, ok := mp[need]; ok {
            if i-j < res { res = i-j }
        }
    }
    if target%sum == 0 { return (target/sum)*n }
    if res == 1<<30 { return -1 }
    return res
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

import java.util.*;
class Solution {
    public int minSizeSubarray(int[] nums, int target) {
        int n = nums.length;
        long sum = 0;
        for (int x : nums) sum += x;
        int res = Integer.MAX_VALUE;
        long[] prefix = new long[2*n+1];
        for (int i = 0; i < 2*n; i++) prefix[i+1] = prefix[i] + nums[i%n];
        Map<Long, Integer> mp = new HashMap<>();
        for (int i = 0; i <= 2*n; i++) mp.put(prefix[i], i);
        for (int i = 0; i <= 2*n; i++) {
            long need = prefix[i] - target;
            if (mp.containsKey(need)) res = Math.min(res, i - mp.get(need));
        }
        if (target % sum == 0) return (int)(target/sum)*n;
        return res == Integer.MAX_VALUE ? -1 : res;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    fun minSizeSubarray(nums: IntArray, target: Int): Int {
        val n = nums.size
        val sum = nums.sum().toLong()
        var res = Int.MAX_VALUE
        val prefix = LongArray(2*n+1)
        for (i in 0 until 2*n) prefix[i+1] = prefix[i] + nums[i%n]
        val mp = mutableMapOf<Long, Int>()
        for (i in 0..2*n) mp[prefix[i]] = i
        for (i in 0..2*n) {
            val need = prefix[i] - target
            if (mp.containsKey(need)) res = minOf(res, i - mp[need]!!)
        }
        if (target % sum == 0L) return (target/sum).toInt()*n
        return if (res == Int.MAX_VALUE) -1 else res
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def minSizeSubarray(self, nums: list[int], target: int) -> int:
        n, s = len(nums), sum(nums)
        if target % s == 0:
            return (target // s) * n
        prefix = [0]
        for i in range(2*n):
            prefix.append(prefix[-1] + nums[i % n])
        mp = {v: i for i, v in enumerate(prefix)}
        res = float('inf')
        for i, v in enumerate(prefix):
            need = v - target
            if need in mp:
                res = min(res, i - mp[need])
        return -1 if res == float('inf') else res
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

use std::collections::HashMap;
impl Solution {
    pub fn min_size_subarray(nums: Vec<i32>, target: i32) -> i32 {
        let n = nums.len();
        let sum: i64 = nums.iter().map(|&x| x as i64).sum();
        if target as i64 % sum == 0 { return (target as i64 / sum * n as i64) as i32; }
        let mut prefix = vec![0i64];
        for i in 0..2*n { prefix.push(prefix.last().unwrap() + nums[i%n] as i64); }
        let mut mp = HashMap::new();
        for (i, &v) in prefix.iter().enumerate() { mp.insert(v, i); }
        let mut res = i32::MAX;
        for (i, &v) in prefix.iter().enumerate() {
            let need = v - target as i64;
            if let Some(&j) = mp.get(&need) {
                res = res.min((i-j) as i32);
            }
        }
        if res == i32::MAX { -1 } else { res }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    minSizeSubarray(nums: number[], target: number): number {
        const n = nums.length, sum = nums.reduce((a,b)=>a+b,0);
        if (target % sum === 0) return Math.floor(target/sum)*n;
        const prefix = [0];
        for (let i = 0; i < 2*n; i++) prefix.push(prefix[prefix.length-1]+nums[i%n]);
        const mp = new Map<number, number>();
        prefix.forEach((v,i)=>mp.set(v,i));
        let res = Infinity;
        for (let i = 0; i < prefix.length; i++) {
            const need = prefix[i] - target;
            if (mp.has(need)) res = Math.min(res, i - mp.get(need)!);
        }
        return res === Infinity ? -1 : res;
    }
}

Complexity

  • ⏰ Time complexity: O(n) — Build prefix sums and hash map.
  • 🧺 Space complexity: O(n) — For prefix sums and hash map.