【迎战蓝桥杯】算法·每日一题（详解+多解）-- day7

苏州程序大白

发布于 2022-05-09 17:46:12

3180

文章被收录于专栏：用户8907256的专栏用户8907256的专栏

【迎战蓝桥杯】算法·每日一题（详解+多解）-- day7

✨博主介绍

🌊 作者主页：苏州程序大白 🌊 作者简介：🏆CSDN人工智能域优质创作者🥇，苏州市凯捷智能科技有限公司创始之一，目前合作公司富士康、歌尔等几家新能源公司

和大于等于 target 的最短子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：输入：target = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：输入：target = 4, nums = [1,4,4] 输出：1
示例 3：输入：target = 11, nums = [1,1,1,1,1,1,1,1] 输出：0

提示：
1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105

进阶：
如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

解题思路

双指针

采用双指针的方式，i不停的向前走，知道sum>=target。
- 当sum<target的时候i++，sum+=nums[i]。
- 当sum==target的时候记录下此时的子数组个数res，并使得i++。
- 当sum>target是，start++，保持i不动，也记录下此时的res（取最小值）。
时间复杂度O(N), 空间复杂度O(1)

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int sum = 0;
        int n=nums.length;
        int res = 0;
        int i=0, start=0;
        while (i<n){
            int cur = sum+nums[i];
            if (cur<target){
                sum += nums[i];
                i++;
            }else if (cur==target){
                sum += nums[i];
                if (res!=0) res = Math.min(res, i-start+1);
                else res = i-start+1;
                i++;
            }else {
                if (res!=0) res = Math.min(res, i-start+1);
                else res = i-start+1;
                sum -= nums[start];
                start++;
            }
        }
        return res;
    }
}

优化

思路与前面大致是一样的，但是更简化
时间复杂度O(N), 空间复杂度O(1)

class Solution {
        public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int ans = Integer.MAX_VALUE;
        int sum = 0;
        int left = 0, right = 0;
        while (right < n) {
            sum += nums[right++];
            while (sum >= target) {
                ans = Math.min(ans, right - left);
                sum -= nums[left++];
            }
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}

前缀和+二分查找

由于数组中元素都是正数，所以前缀和数组为递增数组，可以使用二分法进行查找。

基于数组获得前缀和数组，数组nums的长度为n,为了方便计算，前缀和数组sums长度为n+1,sums[0]=0表示前0个数的和为0，sums[i]表示前i个数的和，sums[i]=nums[0]+nums[1]+……+nums[i-1]。构造前缀和数组的时间复杂度为O(n)。

nums数组中连续数字的和大于等于target,等价于sums数组中sums[j]-sums[i]>=target。

要找到最短连续字数组，首先遍历固定一个数字sum[i]，时间复杂度O(n)。

再在i后面的数中找到一个数sums[j],保证nums[j]>=nums[i]+target且j最小。连续数组找大于或等于目标值的数字，采用二分法，时间复杂度O(nlgn)。

时间复杂度：O(n)+O(nlgn)=O(nlgn) 空间复杂度：O(n)

public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int minLen = Integer.MAX_VALUE;

        int[] sums = new int[n + 1];//前缀和数组，sums[0] = 0,sums[i]为前i个数的和
        for(int i = 1; i <= n; i++) sums[i] = sums[i - 1] + nums[i - 1];
        
        // sums[j]-sums[i] >= target
        for(int i = 0; i < n; i++){
            int num = target + sums[i];
            int j = Arrays.binarySearch(sums, num);//如果数组中存在num，返回索引；如果不存在，返回-（插入索引+1）
            if(j < 0) j = -j-1;//找到大于num的最小位置
            if(j <= n) minLen = Math.min(minLen, j - i);
        }
        return minLen == Integer.MAX_VALUE ? 0 : minLen;
    }

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-05-07，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度