双指针之滑动窗口(长度最小的子数组 和 和为s的连续正数序列)

简介: 双指针之滑动窗口(长度最小的子数组 和 和为s的连续正数序列)

双指针之滑动窗口 (长度最小的子数组;和为s的连续正数序列)

 

1, 什么时候使用?

(与子数组/字符串 有关的题目)~如果给了某个具体值的target,即用滑动窗口

不然就双指针(一般做法,左边< 右边,依据条件左边和右边都不断靠近)

滑动窗口:是双指针的题目
找出一个数组中满足一定条件的子数组问题,字符串也可以看成数组。看到子数组问题,就是DP回溯滑动窗口这三种之一

2,滑动窗口的通用框架 1:(例题:209_长度最小的子数组)

题特点一:题目给定了具体的值target,这个target条件的可能弹性空间比较大了

 【例如题目 要求某种情况下>= target】,而大于target的可能情况就会比较多了


* ① 先移动右指针确定窗口的大致可能范围(在这大致可能范围里找到最优范围),然后暂时固定住右指针,
* ② 在满足条件(满足target下):不断的移动左指针,缩小窗口
* ③ 当不满足target了,又开始移动右指针,然后。。。。。又确定下来窗口的大致可能范围

    (在这大致可能范围里找到最优范围),然后暂时固定住右指针。。。
* 特点2,形式上的特点(左右指针移动的方向):是一开始左右指针,同方法移动)

public class 滑动窗口的通用框架 1{
     public String slidingWindow(String s, String t) {
            // 起始的时候,都位于 0,同方向移动
            int left = 0;
            int right = 0;
            int sLen = s.length();
            while (right < sLen) {
                char c = s.charAt(right);
                right++;
                //对状态做修改
                while ( 满足某种条件 ) {
                   //更新ans可能的地方之一
                    char c1 = s.charAt(left);
                    left++;
                    //对状态做修改
                }
                //更新ans可能的地方之二
            }
            return 需要的结果变量;
        }
}


例题:


package 数组;
/**
 * https://leetcode-cn.com/problems/minimum-size-subarray-sum/
 * @author Huangyujun
 * 
 * 注意细节:当找到满足条件的窗口时,需要固定右边界,
 * 逐渐移动左边界(缩小窗口大小),直到窗口元素和不满足要求,再改变右边界。使用while循环缩小!
 *
 */
public class _209_长度最小的子数组 {
    public int minSubArrayLen(int s, int[] nums) {
        int n = nums.length;
        if (nums == null || n == 0) return 0;
        int ans = Integer.MAX_VALUE;
        int left = 0, right = 0;
        int sum = 0;
        while (right < n) {
            sum += nums[right++];
            while (sum >= s) {
                ans = Math.min(ans, right - left);
                sum -= nums[left++];
            }
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}


3,滑动窗口的通用框架2:(例题:57_和为s的连续正数序列)

做题特点 一:题目给定了具体的值target,这个target条件的可能弹性空间唯一了

【例如题目 要求某种情况下= target】,而等于target的可能情况在“暂时固定下的范围窗口中情况就是固定下该窗口呀”

* ① == target,这种直接通过判断找窗口范围,找到一个固定窗口范围后,移动左边指针(达到整体窗口向前移动)

  去找下一个固定窗口范围

* 这类题:直接分:①== target,② < target ,③ > target 来找合适的固定窗口范围


public class 滑动窗口的通用框架 2{
    public String slidingWindow(int target) {
           // 起始的时候,同方向移动
           int left = 1;
           int right = 2;
           while (l < r) {
                更新ans
                if( ans == target){
                    //需要的结果,得到了一个
                    l++;
                }else if(ans < target){    //比target小,右指针往前移动,扩大范围
                    r++;
                }else{        //比target大,左指针往前移动,缩小范围
                    l++;
                }
           }
           return 需要的结果变量;
       }
}


例题:


package 数组;
/**
 * https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/
 */
import java.util.ArrayList;
import java.util.List;
public class _57_和为s的连续正数序列 {
    /**
     * 细节:正数 思路: 1、双指针技术,就是相当于有一个窗口,窗口的左右两边就是两个指针 2、根据窗口内值之和来确定窗口的位置和宽度。
     */
    public int[][] findContinuousSequence(int target) {
        List<int[]> vec = new ArrayList<int[]>();
        int l = 1, r = 2;
        while(l < r) {
            //求和公式
            int sum = (l + r) * (r - l + 1) / 2;
            if (sum == target) {
                int[] res = new int[r - l + 1];
                for (int i = l; i <= r; ++i) {
                    res[i - l] = i;
                }
                vec.add(res);
                l++;    //找到之后,左边指针往前挪动,意味着整个窗口往前挪动
            } else if (sum < target) {
                r++;
            } else {
                l++;
            }
        }
        return vec.toArray(new int[vec.size()][]);
    }
}


✿ 没给某个具体值的target,使用一般双指针思路(一般做法,左边< 右边,依据条件左边和右边都不断靠近):

例题:(盛最多水的容器)


// https://leetcode-cn.com/problems/container-with-most-water/   //正解:双指针法
    public class Solution {
        public int maxArea(int[] height) {
            int l = 0, r = height.length - 1;
            int ans = 0;
            while (l < r) {
                //面积公式 高:最小的 【左柱子,右柱子】
                int area = Math.min(height[l], height[r]) * (r - l);
                ans = Math.max(ans, area);
                // 需要找小的:(目的:去获取那个小柱子中的最大值)
                if (height[l] <= height[r]) {
                    ++l;
                }
                else {
                    --r;
                }
            }
            return ans;
        }
    }



目录
相关文章
|
1月前
|
存储 算法
LeetCode刷题---209. 长度最小的子数组(双指针-滑动窗口)
LeetCode刷题---209. 长度最小的子数组(双指针-滑动窗口)
|
3月前
|
算法 容器 NoSQL
双指针扫描、滑动窗口
双指针扫描、滑动窗口
|
4月前
|
算法 测试技术 C++
【二分查找】【双指针】LeetCode:2565最少得分子序列
【二分查找】【双指针】LeetCode:2565最少得分子序列
|
人工智能 测试技术 BI
cf1348B phoenix and beauty(双指针滑动窗口)
cf1348B phoenix and beauty(双指针滑动窗口)
49 0
(双指针滑动窗口)AcWing 1238. 日志统计
(双指针滑动窗口)AcWing 1238. 日志统计
59 0
|
机器学习/深度学习
<代码随想录二刷>二分查找 | 双指针 | 滑动窗口 | 枚举模拟(四)
<代码随想录二刷>二分查找 | 双指针 | 滑动窗口 | 枚举模拟
<代码随想录二刷>二分查找 | 双指针 | 滑动窗口 | 枚举模拟(四)
|
存储 算法
<代码随想录二刷>二分查找 | 双指针 | 滑动窗口 | 枚举模拟(三)
<代码随想录二刷>二分查找 | 双指针 | 滑动窗口 | 枚举模拟
<代码随想录二刷>二分查找 | 双指针 | 滑动窗口 | 枚举模拟(三)
|
人工智能
<代码随想录二刷>二分查找 | 双指针 | 滑动窗口 | 枚举模拟(二)
<代码随想录二刷>二分查找 | 双指针 | 滑动窗口 | 枚举模拟
<代码随想录二刷>二分查找 | 双指针 | 滑动窗口 | 枚举模拟(二)
|
算法 索引
<代码随想录二刷>二分查找 | 双指针 | 滑动窗口 | 枚举模拟(一)
<代码随想录二刷>二分查找 | 双指针 | 滑动窗口 | 枚举模拟
<代码随想录二刷>二分查找 | 双指针 | 滑动窗口 | 枚举模拟(一)
|
机器学习/深度学习 索引
438. 找到字符串中所有字母异位词 : 双指针实现滑动窗口
438. 找到字符串中所有字母异位词 : 双指针实现滑动窗口