[LeetCode] 862. Shortest Subarray with Sum at Least K

https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/description/?envType=daily-question&envId=2024-11-17

leetcode - Shortest Subarray with Sum at Least K

문제 유형: 슬라이딩 윈도우, 부분합, 모노토닉 데크

문제 난이도: Hard

 

문제

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.

 

정수 배열 nums와 정수 k가 주어집니다. 부분배열의 합이 k이상이 되는 가장 작은 부분배열의 길이를 구하시오. 없으면 -1을 반환하시오.

 

풀이

요소에 음수도 포함이기 때문에, 일반적인 슬라이딩 윈도우로 푸는 건 불가능하다.

대신, 부분합 및 deque를 넣어서 관찰할 것이다.

 

우선, prefixSum배열을 만든다.

prefixSum[i] = 0번부터 i번이전까지의 요소들의 합이다.

 

매 prefixSum을 순회하면서,

  덱의 앞에서부터 prefixSum[i] - prefixSum[dq.front()]가 k이상인 동안, dq의 요소들을 제거한다.

  이는 유효한 윈도우를 줄여나가면서, 더 최소값을 찾는다는 의미이다.

  윈도우 줄이기를 시도하면서, 최소길이를 업데이트한다.

  

  그리고, 덱의 뒤에서 prefixSum[i]보다 크거나 같은 prefix[dq.back()]의 요소들을 제거한다.

  이는 의미가 없는 답이므로 없앤다는 뜻이다.

  여기가 핵심적인 로직인데, 이 작업으로 데크의 요소들이 오름차순으로 저장되어 있다.(인덱스 말고 부분합을 생각해봤을 때)

 

최종적인 최소길이를 반환한다.

 

코드

C++

#pragma GCC optimize("O3", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    int shortestSubarray(vector<int>& nums, int k) {
        int ans = INT_MAX;
        int n = nums.size();
        vector<long long> prefixSum(n+1, 0);
        for(int i = 0; i < n; ++i) {
            prefixSum[i+1] = prefixSum[i] + nums[i];
        }

        deque<int> dq;
        for(int i = 0; i <= n; ++i) {
            while(!dq.empty() && prefixSum[i] - prefixSum[dq.front()] >= k) {
                ans = min(ans, i - dq.front());
                dq.pop_front();
            }

            while(!dq.empty() && prefixSum[i] <= prefixSum[dq.back()]) {
                dq.pop_back();
            }

            dq.push_back(i);
        }

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