0862-和至少为 K 的最短子数组

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:26 2023-09-13 16:06:26 Updated    

给你一个整数数组 nums 和一个整数 k ，找出 nums 中和至少为 k 的 最短非空子数组
，并返回该子数组的长度。如果不存在这样的 子数组 ，返回 -1 。

子数组 是数组中 连续 的一部分。

示例 1：

**输入：** nums = [1], k = 1
**输出：** 1

示例 2：

**输入：** nums = [1,2], k = 4
**输出：** -1

示例 3：

**输入：** nums = [2,-1,2], k = 3
**输出：** 3

提示：

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

方法一：前缀和 + 单调双端队列

思路

记数组 nums 的前缀和数组为 preSumArr，可以根据 preSumArr}[i] = \sum_{j=0}^{i-1}{nums}[j] 计算得到。对于边界情况，preSumArr}[0] = 0。而从数组 nums 下标 i 开始长为 m 的子数组的和就可以根据 preSumArr}[i+m] - \textit{preSumArr}[i] 快速计算得到。

题目要求计算 nums 中，和大于等于 k 的最短子数组的长度。可以以 nums 的每一个下标作为候选子数组的起点下标，都计算满足条件的最短子数组的长度，然后再从这些长度中找出最小值即可。

遍历 preSumArr 数组，访问过的前缀和先暂存在某种集合 q 中。根据前缀和数组的性质，后访问到的某个前缀和 preSumArr}[j] 减去之前访问到的某个前缀和 preSumArr}[i]（j \gt i）即为 nums 中某段子数组的和。因此，每次访问到某个前缀和 preSumArr}[j] 时，可以用它尝试减去集合 q 中所有已经访问过的前缀和。当某个 q 中的前缀和 preSumArr}[i]，第一次出现 preSumArr}[j] - \textit{preSumArr}[i] \geq k 时，这个下标 i 就找到了以它为起点的最短子数组的长度 j-i。此时，可以将它从 q 中移除，后续即使还有以它为起点的满足条件的子数组，长度也会大于当前的长度。当一个前缀和 preSumArr}[j] 试减完 q 中的元素时，需要将它也放入 q 中。将它放入 q 前， q 中可能存在比 preSumArr}[j] 大的元素，而这些元素和 preSumArr}[j] 一样，只能作为再后续访问到的某个前缀和 preSumArr}[h] 的减数。而作为减数时，更大的值只会让不等式 preSumArr}[h] - \textit{preSumArr}[i] \geq k 更难满足。即使都满足，后访问到的值也可以带来更短的长度。 因此，在把 preSumArr}[j] 放入 q 时，需要将 q 中大于等于 preSumArr}[j] 的值也都移除。

接下来考虑 q 的性质。我们会往 q 中增加和删除元素。每次增加一个元素 curSum 前，先根据不等式删除一部分元素（也可能不删），然后再删除 q 中所有大于等于 curSum 的元素，这样每次加进去的元素都会是 q 中的唯一最大值，使得 q 中的元素是按照添加顺序严格单调递增的，我们知道单调队列是满足这样的性质的。而这一性质，也可以帮助找到 q 中所有满足不等式的值。按照添加的顺序从早到晚，即元素的值从小到大来比较是否满足不等式即可。按照这个顺序，一旦有一个元素不满足，q 中后续的元素也不会满足不等式，即可停止比较。基于此，我们需要一个集合，可以在两端删除元素，在一端添加元素，因此使用双端队列。

在完成代码时，q 中暂存的元素是 preSumArr 的下标，对应下标的前缀和严格单调递增。

代码

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def shortestSubarray(self, nums: List[int], k: int) -> int:
        preSumArr = [0]
        res = len(nums) + 1
        for num in nums:
            preSumArr.append(preSumArr[-1] + num)
        q = deque()
        for i, curSum in enumerate(preSumArr):
            while q and curSum - preSumArr[q[0]] >= k:
                res = min(res, i - q.popleft())
            while q and preSumArr[q[-1]] >= curSum:
                q.pop()
            q.append(i)
        return res if res < len(nums) + 1 else -1
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int shortestSubarray(int[] nums, int k) {
        int n = nums.length;
        long[] preSumArr = new long[n + 1];
        for (int i = 0; i < n; i++) {
            preSumArr[i + 1] = preSumArr[i] + nums[i];
        }
        int res = n + 1;
        Deque<Integer> queue = new ArrayDeque<Integer>();
        for (int i = 0; i <= n; i++) {
            long curSum = preSumArr[i];
            while (!queue.isEmpty() && curSum - preSumArr[queue.peekFirst()] >= k) {
                res = Math.min(res, i - queue.pollFirst());
            }
            while (!queue.isEmpty() && preSumArr[queue.peekLast()] >= curSum) {
                queue.pollLast();
            }
            queue.offerLast(i);
        }
        return res < n + 1 ? res : -1;
    }
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int shortestSubarray(vector<int>& nums, int k) {
        int n = nums.size();
        vector<long> preSumArr(n + 1);
        for (int i = 0; i < n; i++) {
            preSumArr[i + 1] = preSumArr[i] + nums[i];
        }
        int res = n + 1;
        deque<int> qu;
        for (int i = 0; i <= n; i++) {
            long curSum = preSumArr[i];
            while (!qu.empty() && curSum - preSumArr[qu.front()] >= k) {
                res = min(res, i - qu.front());
                qu.pop_front();
            }
            while (!qu.empty() && preSumArr[qu.back()] >= curSum) {
                qu.pop_back();
            }
            qu.push_back(i);
        }
        return res < n + 1 ? res : -1;
    }
};
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
typedef struct {
    int *elements;
    int rear, front;
    int capacity;
} MyCircularDeque;

MyCircularDeque* myCircularDequeCreate(int k) {
    MyCircularDeque *obj = (MyCircularDeque *)malloc(sizeof(MyCircularDeque));
    obj->capacity = k + 1;
    obj->rear = obj->front = 0;
    obj->elements = (int *)malloc(sizeof(int) * obj->capacity);
    return obj;
}

bool myCircularDequeInsertFront(MyCircularDeque* obj, int value) {
    if ((obj->rear + 1) % obj->capacity == obj->front) {
        return false;
    }
    obj->front = (obj->front - 1 + obj->capacity) % obj->capacity;
    obj->elements[obj->front] = value;
    return true;
}

bool myCircularDequeInsertLast(MyCircularDeque* obj, int value) {
    if ((obj->rear + 1) % obj->capacity == obj->front) {
        return false;
    }
    obj->elements[obj->rear] = value;
    obj->rear = (obj->rear + 1) % obj->capacity;
    return true;
}

bool myCircularDequeDeleteFront(MyCircularDeque* obj) {
    if (obj->rear == obj->front) {
        return false;
    }
    obj->front = (obj->front + 1) % obj->capacity;
    return true;
}

bool myCircularDequeDeleteLast(MyCircularDeque* obj) {
    if (obj->rear == obj->front) {
        return false;
    }
    obj->rear = (obj->rear - 1 + obj->capacity) % obj->capacity;
    return true;
}

int myCircularDequeGetFront(MyCircularDeque* obj) {
    if (obj->rear == obj->front) {
        return -1;
    }
    return obj->elements[obj->front];
}

int myCircularDequeGetRear(MyCircularDeque* obj) {
    if (obj->rear == obj->front) {
        return -1;
    }
    return obj->elements[(obj->rear - 1 + obj->capacity) % obj->capacity];
}

bool myCircularDequeIsEmpty(MyCircularDeque* obj) {
    return obj->rear == obj->front;
}

bool myCircularDequeIsFull(MyCircularDeque* obj) {
    return (obj->rear + 1) % obj->capacity == obj->front;
}

void myCircularDequeFree(MyCircularDeque* obj) {
    free(obj->elements);
    free(obj);
}

#define MIN(a, b) ((a) < (b) ? (a) : (b))

int shortestSubarray(int* nums, int numsSize, int k) {
    long preSumArr[numsSize + 1];
    preSumArr[0] = 0;
    for (int i = 0; i < numsSize; i++) {
        preSumArr[i + 1] = preSumArr[i] + nums[i];
    }
    int res = numsSize + 1;
    MyCircularDeque *queue = myCircularDequeCreate(numsSize + 1);
    for (int i = 0; i <= numsSize; i++) {
        long curSum = preSumArr[i];
        while (!myCircularDequeIsEmpty(queue) && curSum - preSumArr[myCircularDequeGetFront(queue)] >= k) {
            res = MIN(res, i - myCircularDequeGetFront(queue));
            myCircularDequeDeleteFront(queue);
        }
        while (!myCircularDequeIsEmpty(queue) && preSumArr[myCircularDequeGetRear(queue)] >= curSum) {
            myCircularDequeDeleteLast(queue);
        }
        myCircularDequeInsertLast(queue, i);
    }
    myCircularDequeFree(queue);
    return res < numsSize + 1 ? res : -1;
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var shortestSubarray = function(nums, k) {
    const n = nums.length;
    const preSumArr = new Array(n + 1).fill(0);
        for (let i = 0; i < n; i++) {
        preSumArr[i + 1] = preSumArr[i] + nums[i];
    }
    let res = n + 1;
    const queue = [];
    for (let i = 0; i <= n; i++) {
        const curSum = preSumArr[i];
        while (queue.length != 0 && curSum - preSumArr[queue[0]] >= k) {
            res = Math.min(res, i - queue.shift());
        }
        while (queue.length != 0 && preSumArr[queue[queue.length - 1]] >= curSum) {
            queue.pop();
        }
        queue.push(i);
    }
    return res < n + 1 ? res : -1;
};
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
func shortestSubarray(nums []int, k int) int {
    n := len(nums)
    preSumArr := make([]int, n+1)
    for i, num := range nums {
        preSumArr[i+1] = preSumArr[i] + num
    }
    ans := n + 1
    q := []int{}
    for i, curSum := range preSumArr {
        for len(q) > 0 && curSum-preSumArr[q[0]] >= k {
            ans = min(ans, i-q[0])
            q = q[1:]
        }
        for len(q) > 0 && preSumArr[q[len(q)-1]] >= curSum {
            q = q[:len(q)-1]
        }
        q = append(q, i)
    }
    if ans < n+1 {
        return ans
    }
    return -1
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 是数组 nums 的长度。求 preSumArr 消耗 O(n)。preSumArr 每个下标会入 q 一次，最多出 q 一次。

  • 空间复杂度：O(n)。preSumArr 和 q 长度均为 O(n)。

 Comments
On this page
0862-和至少为 K 的最短子数组