通知 网站从因情语写改为晴雨,这个网站的模板也从calmlog_ex改为 whimurmur

leetcode探索之数组类算法学习 双索引技巧 - 滑动窗口

4099人浏览 / 0人评论 / | 作者:因情语写  | 分类: 设计模式与算法  | 标签: 设计模式与算法  /  leetcode

作者:因情语写

链接:https://www.qingyu.blue/article/203

声明:请尊重原作者的劳动,如需转载请注明出处


    一些题目用滑动窗口方法解题,可以将时间复杂度控制在 O(n) 级别,最重要的是定义好滑动窗口,明确它要表达的意思,当然边界和初始值非常重要。


    长度最小的子数组

给定一个含有 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的连续子数组如果不存在符合条件的连续子数组,返回 0。

示例: 

输入: s = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。

进阶:

如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。

     说明:使用滑动窗口法,还使用了一个小技巧,在确定子数组长度时用了折半的方法以提高效率

public int minSubArrayLen(int s, int[] nums) {
        int max = slideWindowMax(nums, nums.length);
        if(max < s)
        {
        	return 0;
        }
        
        int low = 1;
        int high = nums.length;
        int mid = low;
        int result = low;
        
        while(low <= high)
        {
        	mid = (low + high) / 2;
        	max = slideWindowMax(nums, mid);
        	if(max < s)
        	{
        		low = mid + 1;
        	}
        	else if(max >= s)
        	{
        		high = mid - 1;
                result = mid;
        	}
        }
        
        return result;
    }
    
    public int slideWindowMax(int[] nums, int length)
    {
        int max = 0;
        int add;
        for(int i = 0; i < length; i++)
        {
        	max += nums[i];
        }
        add = max;
        
        for(int j = length; j < nums.length; j++)
        {
        	add = add - nums[j - length] + nums[j];
        	max = max(add, max);
        }
        
        return max;
    }
    
    public int max(int i, int j)
    {
    	return i >= j ? i : j;
    }

    我能想到的比较好的方法了,结果显示效率并不是太高,让我们看一下更高效的算法

public int minSubArrayLen(int s, int[] nums) {
        int p1=0;
        int p2=0;
        int sum = 0;
        int min = Integer.MAX_VALUE;
        while(p2<nums.length){
            sum+=nums[p2];
            p2++;
            while(sum>=s){
                if(p2-p1<min) min=p2-p1;
                sum-= nums[p1];
                p1++;
            }
        }
        if(min==Integer.MAX_VALUE) return 0;
        else return min;
    }

    这才是真正的滑动窗口啊,我上面的和这一比立马被比下去了,不过代码简洁了,就不是太好理解了,简单来说就是从前向后加的一个子数组如果满足条件,那么可能更短的子数组一定是去头的(去尾不行,因为是尾加满足的,去尾一定会不满足了)

    解题思路

    要求是连续子数组,所以我们必须定义 i,j两个指针,i 向前遍历,j 向后遍历,相当与一个滑块,这样所有的子数组都会在 [i...j] 中出现,如果 nums[i..j] 的和小于目标值 s,那么j向后移一位,再次比较,直到大于目标值 s 之后,i 向前移动一位,缩小数组的长度。遍历到i到数组的最末端,就算结束了,如果不存在符合条件的就返回 0。


    总结

    用了两种滑动法,显示自己写的不太好,而且还是参考别人的

    到这里数组类算法的学习也就完了,以后有时间会做其它的基础的题目并更新的。

    我们知道在准备面试的时候,刷算法题是一种捷径,特别是刷 LeetCode,但是不能一味的刷题,我们需要总结和思考,对于一些相似的题目我们应该多想想他们的思想,其实很多题的解题思路都是相近的。


亲爱的读者:如果你喜欢文章的话,不妨点赞评论支持作者一下吧


点赞(0) 打赏

全部评论

还没有评论!