跳至主要內容

双指针

2023年12月17日大约 6 分钟

双指针

定长滑动窗口

题目难度
1456. 定长子串中元音的最大数目中等1263
643. 子数组最大平均数 I简单
1343. 大小为 K 且平均值大于等于阈值的子数组数目中等1317
2090. 半径为 k 的子数组平均值中等1358
2379. 得到 K 个黑块的最少涂色次数简单1360
1052. 爱生气的书店老板中等1418
2841. 几乎唯一子数组的最大和中等1546
2461. 长度为 K 子数组中的最大和中等1553
1423. 可获得的最大点数中等1574
$1151. 最少交换次数来组合所有的 1中等
2134. 最少交换次数来组合所有的 1 II中等1748
567. 字符串的排列中等
438. 找到字符串中所有字母异位词中等
2953. 统计完全子字符串困难2449 【好题】

不定长滑动窗口（求最长/最大）

题目难度
3. 无重复字符的最长子串中等
1493. 删掉一个元素以后全为 1 的最长子数组中等1423
2730. 找到最长的半重复子字符串中等1502 【好题】
904. 水果成篮中等1516
1695. 删除子数组的最大得分中等1529
2958. 最多 K 个重复元素的最长子数组中等1535
2024. 考试的最大困扰度中等1643
1004. 最大连续 1 的个数 III中等1656
239. 滑动窗口最大值困难
1438. 绝对差不超过限制的最长连续子数组中等1672 【好题】
2401. 最长优雅子数组中等1750 【好题】
1658. 将 x 减到 0 的最小操作数中等1817
1838. 最高频元素的频数中等1876
2516. 每种字符至少取 K 个中等1948
2831. 找出最长等值子数组困难1976
2106. 摘水果困难2062
2781. 最长合法子字符串的长度困难2204 【好题】优化
395. 至少有 K 个重复字符的最长子串中等【好题】分治 和 滑窗
1763. 最长的美好子字符串简单【好题】分治 和 滑窗
$159. 至多包含两个不同字符的最长子串简单
$340. 至多包含 K 个不同字符的最长子串简单

不定长滑动窗口（求最短/最小）

题目难度
209. 长度最小的子数组中等
1234. 替换子串得到平衡字符串中等1878
1574. 删除最短的子数组使剩余数组有序中等1932
76. 最小覆盖子串困难
面试题 17.18. 最短超串中等

不定长滑动窗口（求子数组个数）

TODO

多指针滑动窗口

TODO

非滑窗

题目难度
524. 通过删除字母匹配到字典里最长单词中等
167. 两数之和 II - 输入有序数组中等
15. 三数之和中等
1031. 两个非重叠子数组的最大和中等双指针 + 动态规划
1477. 找两个和为目标值且不重叠的子数组中等双指针 + 动态规划
2555. 两个线段获得的最多奖品中等双指针 + 动态规划
CF1154Erating 1800双指针 + 动态规划

类型

codeforces 上只有 two pointers 标签，没有滑动窗口的说法。

524. 通过删除字母匹配到字典里最长单词

import java.util.List;

public class Solution524 {
    public String findLongestWord(String s, List<String> dictionary) {
        String res = "";
        for (String t : dictionary) {
            // 双指针 判断 每个 t 是否为 s 的一个子序列
            int p1 = 0;
            int p2 = 0;
            while (p1 < s.length() && p2 < t.length()) {
                if (s.charAt(p1) == t.charAt(p2)) {
                    p2++;
                }
                p1++;
            }
            if (p2 == t.length()) {
                // 遇到长度更长 或者 相同长度但字典序更小 时更新 res
                if (t.length() > res.length() || (t.length() == res.length() && t.compareTo(res) < 0)) {
                    res = t;
                }
            }
        }
        return res;
    }
}

167. 两数之和 II - 输入有序数组

public class Solution167 {
    public int[] twoSum(int[] numbers, int target) {
        int left = 0;
        int right = numbers.length - 1;
        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                return new int[]{left + 1, right + 1};
            } else if (sum < target) {
                ++left;
            } else {
                --right;
            }
        }
        return new int[]{-1, -1};
    }
}

15. 三数之和

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution15 {
    public List<List<Integer>> threeSum(int[] nums) {
        int len = nums.length;
        if (len < 3) {
            return new ArrayList<>();
        }

        Arrays.sort(nums);
        List<List<Integer>> resList = new ArrayList<>();

        for (int i = 0; i < len - 2; i++) {
            // 剪枝
            if (i - 1 >= 0 && nums[i - 1] == nums[i]) {
                continue;
            }

            // 双指针
            int left = i + 1;
            int right = len - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0) {
                    resList.add(List.of(nums[i], nums[left], nums[right]));

                    // 移动到下一个不相等的元素
                    int l0 = left + 1;
                    while (l0 < right && nums[l0] == nums[left]) {
                        l0++;
                    }
                    left = l0;
                } else if (sum < 0) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return resList;
    }
}

1031. 两个非重叠子数组的最大和

public class Solution1031 {
    public int maxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) {
        return Math.max(dp(nums, firstLen, secondLen), dp(nums, secondLen, firstLen));
    }

    private int dp(int[] nums, int firstLen, int secondLen) {
        int n = nums.length;
        // f[i] 表示 [0, i) 之间长为 firstLen 的最大和
        int[] f = new int[n + 1];
        int l = 0, r = 0, sum = 0, max = 0;
        while (r < n) {
            sum += nums[r];
            while (r - l + 1 > firstLen) sum -= nums[l++];
            max = Math.max(max, sum);
            f[r + 1] = Math.max(f[r], max);
            r++;
        }
        r = l = sum = max = 0;
        while (r < n) {
            sum += nums[r];
            while (r - l + 1 > secondLen) sum -= nums[l++];
            max = Math.max(max, sum + f[l]);
            r++;
        }
        return max;
    }
}

1477. 找两个和为目标值且不重叠的子数组

public class Solution1477 {
    public int minSumOfLengths(int[] arr, int target) {
        int n = arr.length;

        // f[i] 表示 [0, i) 之间最短的和为 target 的子数组长度
        int[] f = new int[n + 1];
        f[0] = n + 1;

        int l = 0, r = 0;
        int sum = 0;
        int min = n + 1;
        while (r < n) {
            sum += arr[r];
            while (sum > target) {
                sum -= arr[l];
                l++;
            }
            if (sum == target) {
                min = Math.min(min, (r - l + 1) + f[l]);
                f[r + 1] = Math.min(f[r], r - l + 1);
            } else {
                f[r + 1] = f[r];
            }
            r++;
        }
        return (min == n + 1) ? -1 : min;
    }
}

2555. 两个线段获得的最多奖品

public class Solution2555 {
    public int maximizeWin(int[] prizePositions, int k) {
        int n = prizePositions.length;

        // f[i] 表示 [0, i) 线段长度 <= k 的最多奖品数
        int[] f = new int[n + 1];

        int l = 0, r = 0;
        int res = 0;
        while (r < n) {
            while (prizePositions[r] - prizePositions[l] > k) {
                l++;
            }
            res = Math.max(res, (r - l + 1) + f[l]);
            f[r + 1] = Math.max(f[r], r - l + 1);
            r++;
        }
        return res;
    }
}

（全文完）

Copyright © 2018-2025 gdut-yy