【每日一题Day8】LC862和至少为K的最短子数组

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

*和至少为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)
目录
相关文章
|
6月前
【每日一题Day159】LC1638统计只差一个字符的子串数目 | 枚举
【每日一题Day159】LC1638统计只差一个字符的子串数目 | 枚举
39 0
|
6月前
【每日一题Day161】LC1641统计字典序元音字符串的数目 | 数位dp
【每日一题Day161】LC1641统计字典序元音字符串的数目 | 数位dp
48 0
|
6月前
【每日一题Day191】LC2423删除字符使频率相同 | 枚举 分类讨论
【每日一题Day191】LC2423删除字符使频率相同 | 枚举 分类讨论
50 0
|
6月前
【每日一题Day179】LC1157子数组中占绝大多数的元素 | 线段树
【每日一题Day179】LC1157子数组中占绝大多数的元素 | 线段树
52 0
|
算法
【代码随想录】LC 209. 长度最小的子数组
利用两层循环,第一层循环枚举子数组的起点位置,第二层循环枚举子数组的终点位置,第二层循环中可以同时来统计当前子数组的和,如果符合题目条件则更新length,否则继续循环,直至两层循环结束,返回题目要求的值,算法结束。
59 0
|
6月前
【每日一题Day160】LC1092最短公共超序列 | 动态规划
【每日一题Day160】LC1092最短公共超序列 | 动态规划
40 0
【每日一题Day160】LC1092最短公共超序列 | 动态规划
|
6月前
【每日一题Day152】LC1012至少有1位重复的数字 | 数位dp
【每日一题Day152】LC1012至少有1位重复的数字 | 数位dp
51 0
|
算法
代码随想录算法训练营第五十二天 | LeetCode 300. 最长递增子序列、674. 最长连续递增序列、718. 最长重复子数组
代码随想录算法训练营第五十二天 | LeetCode 300. 最长递增子序列、674. 最长连续递增序列、718. 最长重复子数组
49 1
|
6月前
【每日一题Day233】LC1170比较字符串最小字母出现频次 | 前缀和
【每日一题Day233】LC1170比较字符串最小字母出现频次 | 前缀和
39 0
|
6月前
【每日一题Day129】LC1247交换字符使得字符串相同 | 贪心
【每日一题Day129】LC1247交换字符使得字符串相同 | 贪心
52 0