*和至少为K的最短子数组【LC862】
给你一个整数数组 nums 和一个整数 k ，找出 nums 中和至少为 k 的 最短非空子数组 ，并返回该子数组的长度。如果不存在这样的 子数组 ，返回 -1 。
子数组 是数组中 连续 的一部分。
今天只能想到超时的做法，想到用单调栈却不知道怎么维护，看题解有C++用单调栈，再结合官题的双端队列，终于写出来了0.0
- 思路：将数组的前i个数字之和记为sum，如果数组中从第i+1个数字开始到第j个数字结束的子数组之和大于等于k，那么数组的前i个数字之和小于等于为sum-k。
- 如何快速搜索是否有前j个数字之和小于等于sum-k以及下标？
- 使用hashmap记录前j个数字之和以及下标，然后通过for循环遍历查找map中是否存在[minSum,sum-k]【超时】
- 单调栈+二分查找?->不能通过下标形式查找所需值，因此不能够实现
- 双端队列
前缀和+暴力搜索【超时】
class Solution { public int shortestSubarray(int[] nums, int k) { int len = nums.length; int[] sums = new int[len+1];// 记录nums[0,i-1]的子数组和 for (int i = 0; i < len; i++){ sums[i+1] = sums[i] + nums[i]; } int minLen = Integer.MAX_VALUE; for (int i = 0; i < len; i++){ for (int j = i; j < len;j++){ int subSum = sums[j+1] - sums[i]; if (subSum >= k){ minLen = Math.min(minLen,j - i + 1); } } } return minLen == Integer.MAX_VALUE ? -1 :minLen; } }
- 复杂度
。时间复杂度：最差O(n2)
。空间复杂度：O(n)
前缀和+HashMap【超时】
- 实现：使用hashmap记录前j个数字之和以及下标，然后通过for循环遍历查找map中是否存在[minSum,sum-k]【超时】
。代码
class Solution { public int shortestSubarray(int[] nums, int k) { Map<Integer,Integer> sumToIndex = new HashMap<>(); sumToIndex.put(0,-1); int len = nums.length; int sum = 0;// 记录子数组nums[0,i]的和 int minSum = 0;// 记录前i个子数组nums[0,i]和的最小值 int minLen = Integer.MAX_VALUE; for (int i = 0; i < len; i++){ sum += nums[i]; int target = sum - k; if (minSum <= target){// 存在前j个数字之和小于等于sum-k for (int n = minSum; n <= target; n++){ if (sumToIndex.containsKey(n)){ minLen = Math.min(minLen,i - sumToIndex.get(n)); } } } sumToIndex.put(sum,i); minSum = Math.min(minSum,sum); } return minLen == Integer.MAX_VALUE ? -1 :minLen; } }
。复杂度
- 时间复杂度：最差O(n2)
- 空间复杂度：O(n)
前缀和+双端队列
- 实现：双端队列存储元素下标
。从头部到尾部下标对应的前缀和的顺序为递增
。当头部元素存储的下标i对应的前缀和sum[i]小于等于当前遍历的元素sums[j]-k时，更新minLen=min(minLen,j-i)，并将其弹出
- 为什么弹出不影响后续结果？因为后续节点的j‘-i一定大于j-i，因此一定不会影响结果
。当尾部元素存储的前缀和大于当前遍历的元素sums[j]时，将其弹出
- 我们需要保持队列递增
。把sums[j]压入队列尾部，保证sums[j]是队列最大的元素
。代码
class Solution { public int shortestSubarray(int[] nums, int k) { int len = nums.length; long[] sums = new long[len + 1]; for (int i = 0; i < len; i++) { sums[i + 1] = sums[i] + nums[i]; } int minLen = Integer.MAX_VALUE; Deque<Integer> st = new LinkedList<>(); for (int i = 0; i <= len; i++){ long curSum = sums[i]; while (!st.isEmpty() && sums[st.peekFirst()] <= curSum - k ){ minLen = Math.min(minLen,i-st.pollFirst()); } while (!st.isEmpty() && curSum <= sums[st.peekLast()]){ st.pollLast(); } st.addLast(i); } return minLen == Integer.MAX_VALUE ? -1 :minLen; } }
。复杂度
- 时间复杂度：O(n)
- 空间复杂度：O(n)
