Skip to content

Latest commit

 

History

History
216 lines (177 loc) · 5.03 KB

File metadata and controls

216 lines (177 loc) · 5.03 KB
comments difficulty edit_url tags
true
Hard
Queue
Array
Binary Search
Prefix Sum
Sliding Window
Monotonic Queue
Heap (Priority Queue)

中文文档

Description

Given an integer array nums and an integer k, return the length of the shortest non-empty subarray of nums with a sum of at least k. If there is no such subarray, return -1.

A subarray is a contiguous part of an array.

 

Example 1:

Input: nums = [1], k = 1
Output: 1

Example 2:

Input: nums = [1,2], k = 4
Output: -1

Example 3:

Input: nums = [2,-1,2], k = 3
Output: 3

 

Constraints:

  • 1 <= nums.length <= 105
  • -105 <= nums[i] <= 105
  • 1 <= k <= 109

Solutions

Solution 1

Python3

class Solution:
    def shortestSubarray(self, nums: List[int], k: int) -> int:
        s = list(accumulate(nums, initial=0))
        q = deque()
        ans = inf
        for i, v in enumerate(s):
            while q and v - s[q[0]] >= k:
                ans = min(ans, i - q.popleft())
            while q and s[q[-1]] >= v:
                q.pop()
            q.append(i)
        return -1 if ans == inf else ans

Java

class Solution {
    public int shortestSubarray(int[] nums, int k) {
        int n = nums.length;
        long[] s = new long[n + 1];
        for (int i = 0; i < n; ++i) {
            s[i + 1] = s[i] + nums[i];
        }
        Deque<Integer> q = new ArrayDeque<>();
        int ans = n + 1;
        for (int i = 0; i <= n; ++i) {
            while (!q.isEmpty() && s[i] - s[q.peek()] >= k) {
                ans = Math.min(ans, i - q.poll());
            }
            while (!q.isEmpty() && s[q.peekLast()] >= s[i]) {
                q.pollLast();
            }
            q.offer(i);
        }
        return ans > n ? -1 : ans;
    }
}

C++

class Solution {
public:
    int shortestSubarray(vector<int>& nums, int k) {
        int n = nums.size();
        vector<long> s(n + 1);
        for (int i = 0; i < n; ++i) s[i + 1] = s[i] + nums[i];
        deque<int> q;
        int ans = n + 1;
        for (int i = 0; i <= n; ++i) {
            while (!q.empty() && s[i] - s[q.front()] >= k) {
                ans = min(ans, i - q.front());
                q.pop_front();
            }
            while (!q.empty() && s[q.back()] >= s[i]) q.pop_back();
            q.push_back(i);
        }
        return ans > n ? -1 : ans;
    }
};

Go

func shortestSubarray(nums []int, k int) int {
	n := len(nums)
	s := make([]int, n+1)
	for i, x := range nums {
		s[i+1] = s[i] + x
	}
	q := []int{}
	ans := n + 1
	for i, v := range s {
		for len(q) > 0 && v-s[q[0]] >= k {
			ans = min(ans, i-q[0])
			q = q[1:]
		}
		for len(q) > 0 && s[q[len(q)-1]] >= v {
			q = q[:len(q)-1]
		}
		q = append(q, i)
	}
	if ans > n {
		return -1
	}
	return ans
}

TypeScript

function shortestSubarray(nums: number[], k: number): number {
    const [n, MAX] = [nums.length, Number.POSITIVE_INFINITY];
    const s = Array(n + 1).fill(0);
    const q: number[] = [];
    let ans = MAX;

    for (let i = 0; i < n; i++) {
        s[i + 1] = s[i] + nums[i];
    }

    for (let i = 0; i < n + 1; i++) {
        while (q.length && s[i] - s[q[0]] >= k) {
            ans = Math.min(ans, i - q.shift()!);
        }

        while (q.length && s[i] <= s[q.at(-1)!]) {
            q.pop();
        }

        q.push(i);
    }

    return ans === MAX ? -1 : ans;
}

JavaScript

function shortestSubarray(nums, k) {
    const [n, MAX] = [nums.length, Number.POSITIVE_INFINITY];
    const s = Array(n + 1).fill(0);
    const q = [];
    let ans = MAX;

    for (let i = 0; i < n; i++) {
        s[i + 1] = s[i] + nums[i];
    }

    for (let i = 0; i < n + 1; i++) {
        while (q.length && s[i] - s[q[0]] >= k) {
            ans = Math.min(ans, i - q.shift());
        }

        while (q.length && s[i] <= s[q.at(-1)]) {
            q.pop();
        }

        q.push(i);
    }

    return ans === MAX ? -1 : ans;
}