DEV Community
·
862. 和至少为K的最短子数组
💡
原文英文，约700词，阅读约需3分钟。
📝
内容提要
给定一个整数数组和一个整数k，要求返回和至少为k的最短非空子数组的长度。如果不存在这样的子数组，返回-1。可以使用前缀和、单调队列和滑动窗口的方法，以O(n)的时间复杂度和O(n)的空间复杂度高效查找满足条件的子数组。
🎯
关键要点
- 给定一个整数数组和一个整数k，要求返回和至少为k的最短非空子数组的长度。
- 如果不存在这样的子数组，返回-1。
- 子数组是数组的连续部分。
- 使用前缀和、单调队列和滑动窗口的方法，以O(n)的时间复杂度和O(n)的空间复杂度高效查找满足条件的子数组。
- 前缀和数组用于计算任意子数组的和。
- 单调队列用于维护前缀和数组的索引，以便高效查找满足条件的子数组。
- 滑动窗口逻辑用于检查当前前缀和与之前前缀和的差值是否大于或等于k。
- 如果找到有效的子数组，返回最小子数组长度；否则返回-1。
- 时间复杂度为O(n)，空间复杂度为O(n)。
➡️
