滑动窗口算法

2023-12-07数据结构与算法4 分钟114 次阅读
AI 摘要salmon-ai

本

简介

滑动窗口是一种双指针算法。它指的是这样一类问题的求解方法,在数组上通过双指针同向移动而解决的一类问题。其实这样的问题我们可以不必为它们专门命名一个名字,它们的解法其实是很自然的。

使用滑动窗口解决的问题通常是暴力解法的优化,掌握这一类问题最好的办法就是练习,然后思考清楚为什么可以使用滑动窗口。

力扣相关算法题:https://leetcode.cn/tag/sliding-window/problemset/

应用场景

关键词

  1. 满足 xxx 条件(计算结果,出现次数,同时包含)
  2. 最长/最短
  3. 子串/子数组/子序列(通常连续)

例如:长度最小的子数组

使用思路

示例图解

image.png

示例演示

iShot_20231207_15.22.51 onlinevideocutter.com.gif

寻找最长

  • 核心: 左右双指针(L,R)在起始点,R 向右逐位滑动循环
  • 每次滑动过程中:
    • 如果:窗内元素满足条件,R 向右扩大窗口,并更新最优结果
    • 如果:窗内元素不满足条件,L 向右缩小窗口
  • R 到达结尾

寻找最短

  • 核心: 左右双指针(L,R)在起始点,R 向右逐位滑动循环
  • 每次滑动过程中:
    • 如果:窗内元素满足条件,L 向右缩小窗口,并更新最优结果
    • 如果:窗内元素不满足条件,R 向右扩大窗口
  • R 到达结尾

解题模板

最长模板

c++ 复制代码
初始化变量 left, right, result, bestResult
while (right 没有到达结尾) {
    窗口扩大,加入right对应元素,更新当前 result
    while (result 不满足要求) {
        窗口缩小,移除 left 对应元素,left 右移
    }
    更新最优结果 bestResult
    right++;
}
return bestResult

最短模板

c++ 复制代码
初始化变量 left, right, result, bestResult
while (right 没有到达结尾) {
    窗口扩大,加入right对应元素,更新当前 result
    while (result 满足要求) {
        更新最优结果 bestResult
        窗口缩小,移除 left 对应元素,left 右移
    }
    right++;
}
return bestResult

例题

长度最小的子数组

题目:209.长度最小的子数组

给定一个含有 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

解法

java 复制代码
/**
 * 209. 长度最小的子数组
 * https://leetcode.cn/problems/minimum-size-subarray-sum/
 *
 * @author Salmon
 * @since 2023-12-07
 */
public class M_209 {
    public static void main(String[] args) {
        System.out.println(minSubArrayLen(7, new int[]{2, 3, 1, 2, 4, 3}));
        System.out.println(minSubArrayLen(4, new int[]{1, 4, 4}));
        System.out.println(minSubArrayLen(11, new int[]{1, 1, 1, 1, 1, 1, 1, 1}));
    }

    public static int minSubArrayLen(int target, int[] nums) {
        int right = 0, left = 0, curSum = 0, minLength = 0;
        // 判断 right 是否到达结尾
        while (right < nums.length) {
            curSum += nums[right];
            // 判断当前是否满足条件,满足条件则进入循环
            // 判断每次缩小后的窗口是否满足满足条件
            while (curSum >= target) {
                // 更新当前窗口中的数组长度,minLength=0:第一次满足条件时需更新下最短长度
                if (minLength == 0 || right - left + 1 < minLength) {
                    minLength = right - left + 1;
                }
                // 缩小窗口
                curSum -= nums[left];
                // 左指针右移
                left++;
            }
            right++;
        }

        return minLength;
    }
}

重复的DNA序列

题目:187. 重复的DNA序列

DNA序列 由一系列核苷酸组成,缩写为 'A', 'C', 'G' 和 'T'.。

  • 例如,"ACGAATTCCG" 是一个 DNA序列 。

在研究 DNA 时,识别 DNA 中的重复序列非常有用。

给定一个表示 DNA序列 的字符串 s ,返回所有在 DNA 分子中出现不止一次的 长度为 10 的序列(子字符串)。你可以按 任意顺序 返回答案。

示例 1:
输入:s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
输出:["AAAAACCCCC","CCCCCAAAAA"]

示例 2:
输入:s = "AAAAAAAAAAAAA"
输出:["AAAAAAAAAA"]

提示:

  • 0 <= s.length <= 105
  • s[i]=='A'、'C'、'G' or 'T'

解法1:直接使用 hash 表统计,简单。

java 复制代码
import java.util.*;

/**
 * 187. 重复的DNA序列
 * https://leetcode.cn/problems/repeated-dna-sequences/
 *
 * @author Salmon
 * @since 2023-12-07
 */
public class M_187 {
    static final int L = 10;

    public static void main(String[] args) {
        List<String> sequences = findRepeatedDnaSequences("AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT");
        System.out.print("[");
        for (int i = 0; i < sequences.size(); i++) {
            System.out.print(sequences.get(i));
            if (i < sequences.size() - 1) {
                System.out.print(",");
            }
        }
        System.out.println("]");
    }

    public static List<String> findRepeatedDnaSequences(String s) {
        List<String> res = new ArrayList<>();
        int n = s.length();
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i <= n - L; ++i) {
            String sub = s.substring(i, i + L);
            map.put(sub, map.getOrDefault(sub, 0) + 1);
            if (map.get(sub) == 2) {
                res.add(sub);
            }
        }
        return res;
    }
}

解法2:哈希表 + 滑动窗口 + 位运算

java 复制代码
import java.util.*;

/**
 * 187. 重复的DNA序列
 * https://leetcode.cn/problems/repeated-dna-sequences/
 *
 * @author Salmon
 * @since 2023-12-07
 */
public class M_187 {

    public static void main(String[] args) {
        List<String> sequences = findRepeatedDnaSequences1("AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT");
//        List<String> sequences = findRepeatedDnaSequences1("AAAAAAAAAAA");
        System.out.print("[");
        for (int i = 0; i < sequences.size(); i++) {
            System.out.print(sequences.get(i));
            if (i < sequences.size() - 1) {
                System.out.print(",");
            }
        }
        System.out.println("]");
    }

    static final int L = 10;

    static Map<Character, Integer> bin = new HashMap<Character, Integer>() {{
        put('A', 0);
        put('C', 1);
        put('G', 2);
        put('T', 3);
    }};

    public static List<String> findRepeatedDnaSequences1(String s) {
        List<String> res = new ArrayList<>();
        int n = s.length();
        if (n <= L) {
            return res;
        }
        int x = 0;
        // 初始化:先累计前 9 个的序列数值
        for (int i = 0; i < L - 1; i++) {
            // 求 x左移2位相当于x乘2的平方 然后与当前字符的映射值作或运算
            x = (x << 2) | bin.get(s.charAt(i));
        }
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i <= n - L; i++) {
            // 将当前的 x 与第10个数字的
            x = ((x << 2) | bin.get(s.charAt(i + L - 1))) & ((1 << (L * 2)) - 1);

            map.put(x, map.getOrDefault(x, 0) + 1);
            // 如果重复出现
            if (map.get(x) == 2) {
                res.add(s.substring(i, i + L));
            }
        }
        return res;
    }
}
觉得有用就点个赞,不用登录也能读

评论

0 条
登录 之后才能评论
—
还没有评论,来说第一句