蓝桥杯第十五届抱佛脚（三）枚举法与尺取法

蓝桥杯第十五届抱佛脚（三）枚举法与尺取法

很多人将蓝桥杯戏称为“暴力杯”，因为蓝桥杯采用了OI的赛制。在这种赛制下，即使对于某些大题答案不清楚的情况下，也可以通过暴力方法获得部分分数。一提到暴力，人们往往首先想到的是枚举。然而，实际上，枚举是一门需要技巧的技术，确保能够穷尽所有可能情况并不容易。因此，在本文中，我将详细介绍枚举法和双指针法的核心思想和算法模板，以确保能够完整地列举出所有情况，不漏掉任何一种可能性。

枚举法

当我们面对一个问题时，如果问题的解空间相对较小，我们可以尝试使用枚举算法来解决。枚举算法的思想非常简单： 逐一检查或列举所有可能的情况，并找出符合问题要求的解。这种方法虽然直观简单，但在某些情况下却是非常有效的。

枚举算法解题的基本思路：

1. 确定枚举解的范围和判断条件： 在开始解题之前，需要明确枚举的解范围，并定义问题的判断条件。
2. 选取合适的枚举方法： 选择适当的枚举方式进行逐一枚举，确保覆盖所有可能的解。避免遗漏任何真正的解，同时注意防止重复。
3. 使用判断条件检验解： 在枚举过程中，应用事先确定的判断条件验证每个解的合法性，保留符合要求的解。

实现枚举算法的基本步骤如下:

1. 确定需要枚举的对象: 首先，你需要明确问题中需要枚举的是什么对象或状态。比如说，如果是求一个数的所有因子，那么需要枚举的就是这个数的所有可能因子；如果是求一组数中所有和为特定值的两个数的组合，那么需要枚举的就是这组数中所有两两组合。

2. 设计枚举顺序和方式: 接下来，你需要设计一种合理的枚举顺序或方式，以避免重复枚举。比如说，如果是求一个数的所有因子，可以从1开始枚举到这个数的平方根；如果是求一组数中所有和为特定值的两个数的组合，可以使用两重循环，外层循环枚举第一个数，内层循环枚举第二个数。

3. 检查每种情况是否满足要求: 对于每一种被枚举到的情况，你需要检查它是否满足问题的要求。比如说，如果是求一个数的所有因子，那么对于每一个被枚举到的数，检查它是否能整除这个数；如果是求和为特定值的两个数的组合，那么对于每一对被枚举到的两个数，检查它们的和是否等于目标值。

4. 记录或更新符合要求的解: 如果一种被枚举到的情况满足问题要求，那么你需要以某种方式记录或更新这个解。比如说，如果是求一个数的所有因子，那么可以把这个数记录到一个数组或集合中；如果是求和为特定值的两个数的组合，那么可以把这对数的索引或值记录到一个数组或集合中。

下面通过一个简单的例子来具体说明枚举算法的实现过程。

例题:给定一个只包含正整数的数组nums和一个正整数target，请找出nums中所有和为target的两个数的组合。

List<int[]> findSumPairs(int[] nums, int target) {
    List<int[]> result = new ArrayList<>();
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] == target) {
                result.add(new int[]{nums[i]， nums[j]});
            }
        }
    }
    return result;
}

让我们逐步分析这个实现:

1. 我们首先确定需要枚举的对象是nums中的两个数的组合。
2. 我们使用两重循环来枚举这些组合，外层循环枚举第一个数，内层循环枚举第二个数。为了避免重复枚举，内层循环的起始位置是i + 1。
3. 对于每一对被枚举到的两个数nums[i]和nums[j]，我们检查它们的和是否等于target。
4. 如果满足要求，我们就把这对数的元组(nums[i]， nums[j])添加到结果列表result中。

最后，我们返回存储了所有符合要求的解的列表result。

注意，枚举算法的时间复杂度通常较高，因为它需要检查所有可能的情况。在这个例子中，时间复杂度是O(n^2)，因为我们使用了两重循环。但是，对于规模较小的问题，枚举算法通常是一种简单有效的解决方案。

简单型枚举

简单型枚举是通过简单的 for 循环嵌套解决的问题类型。因此，简单型枚举是一种相对简单且大家接触最多的枚举方式。这是最基础的枚举法，就是直接枚举所有可能的情况。通常用在问题规模较小，可能情况有限的情况下。

实现步骤:

• 确定需要枚举的对象
• 使用嵌套循环或递归直接枚举所有可能情况
• 检查每种情况是否满足要求
• 记录符合要求的解

这种枚举方式没有特定的固定枚举模式，而且相对简单。只需按照题目的要求设计代码即可完成解题。

例子： 查找数组中的最大值

使用技巧：

• 遍历数组，逐个比较元素，记录当前最大值。
• 初始时将最大值设置为数组的第一个元素。
• 在遍历过程中，不断更新最大值，直到遍历完整个数组。

int[] nums = {5, 3, 9, 2, 7};
int max = nums[0]; // 初始最大值为数组的第一个元素
for (int i = 1; i < nums.length; i++) {
    if (nums[i] > max) {
        max = nums[i]; // 更新最大值
    }
}
System.out.println("数组中的最大值为：" + max);

组合型枚举

排列组合是大家都接触过的概念，而组合型枚举则是在 n 个元素中随机选出 m 个元素的问题。对于每一种可能的选择方案，我们需要确定选择了哪 m 个元素，这就是组合型枚举。

实现步骤:

• 确定需要枚举的对象(通常是从集合中选取k个元素的所有组合)
• 使用嵌套循环或递归枚举所有组合
• 检查每种组合是否满足要求
• 记录符合要求的组合

例子： 输出字符串的所有子集

使用技巧：

• 使用递归方法生成子集。
• 对于每个字符，可以选择包含或不包含在子集中。
• 递归地生成包含当前字符的子集和不包含当前字符的子集，直到遍历完整个字符串。

public void generateSubsets(String s, String subset, int index) {
    if (index == s.length()) {
        System.out.println(subset); // 输出当前子集
        return;
    }
    generateSubsets(s, subset + s.charAt(index)， index + 1); // 包含当前字符
    generateSubsets(s, subset, index + 1); // 不包含当前字符
}

String str = "abc";
generateSubsets(str, ""， 0); // 调用函数生成所有子集

具体而言，组合型枚举解决的是 Cnm 问题，即从 n 个元素中选择 m 个元素的组合数量。

组合型枚举是一种在一组元素中选择若干个元素形成不同组合的枚举方法。其固定的流程和算法模板可以总结如下：

固定流程

1. 确定问题的解空间： 确定需要进行组合枚举的元素集合，通常是一个数组或集合。

2. 选择元素个数范围： 确定每个组合中包含的元素个数范围，通常是从1到元素总数的范围。

3. 使用递归或迭代方式生成组合： 对于每个可能的元素组合，递归或迭代生成组合，并对每种组合进行处理。

4. 根据问题需求处理组合： 对于每种生成的组合，根据具体问题需求进行处理，例如计算组合的和、检查组合是否满足条件等。

算法模板

下面是一个基于递归的组合型枚举的算法模板：

public void generateCombinations(int[] nums, List<Integer> combination, int start, int k) {
    // 递归终止条件：当组合中元素个数达到k时
    if (combination.size() == k) {
        // 处理当前组合，例如输出或其他操作
        System.out.println(combination);
        return;
    }
    // 递归生成组合
    for (int i = start; i < nums.length; i++) {
        combination.add(nums[i]); // 添加当前元素到组合中
        generateCombinations(nums, combination, i + 1, k); // 递归生成剩余元素的组合
        combination.remove(combination.size() - 1); // 回溯，移除当前元素
    }
}

1. generateCombinations 方法接收参数包括原始数组 nums，当前组合 combination，起始位置 start，以及组合中元素个数 k。

2. 当组合中的元素个数等于 k 时，递归终止，处理当前组合。可以根据具体需求进行输出或其他操作。

3. 在每次递归中，遍历从 start 开始到数组末尾的所有元素，依次将当前元素添加到组合中，并递归生成剩余元素的组合。

4. 在递归返回后，执行回溯操作，将当前元素移除，继续尝试其他元素。

5. 最后，调用函数时传入原始数组、一个空的组合、起始位置和组合中元素个数，生成所有符合条件的组合。

例题：组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1：

输入：n = 4, k = 2
输出：
[
  [2,4]，
  [3,4]，
  [2,3]，
  [1,2]，
  [1,3]，
  [1,4]，
]

示例 2：

输入：n = 1, k = 1
输出：[[1]]

使用模板解决：

我们直接使用组合型枚举的算法模板来解决这个问题。具体步骤如下：

1. 使用递归的方式生成所有可能的组合。
2. 确定组合中的元素个数为 k。
3. 确定组合的起始位置为 1。
4. 根据递归终止条件，在组合中的元素个数达到 k 时，输出当前组合。

代码示例：

public class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<>();
        generateCombinations(result, new ArrayList<>()， 1, n, k);
        return result;
    }
    private void generateCombinations(List<List<Integer>> result, List<Integer> combination, int start, int n, int k) {
        // 递归终止条件：组合中的元素个数达到k时
        if (combination.size() == k) {
            result.add(new ArrayList<>(combination)); // 将当前组合添加到结果中
            return;
        }
        // 递归生成组合
        for (int i = start; i <= n; i++) {
            combination.add(i); // 添加当前元素到组合中
            generateCombinations(result, combination, i + 1, n, k); // 递归生成剩余元素的组合
            combination.remove(combination.size() - 1); // 回溯，移除当前元素
        }
    }
}

排列型枚举

排列型枚举相对组合型枚举就简单了一点，就是 n 个的全排列，即从 n 个中选取 n 个但是关心内部的顺序。

这种枚举法需要枚举一个集合中元素的所有排列情况。

实现步骤:

• 确定需要枚举的对象(通常是一个集合中元素的所有排列)
• 使用递归或基于交换的方法生成所有排列
• 检查每种排列是否满足要求
• 记录符合要求的排列

例子： 输出字符串的所有排列

使用技巧：

• 使用递归方法生成排列。
• 对于每个位置，可以选择当前字符及其余字符进行排列。
• 递归地生成剩余字符的排列，直到遍历完整个字符串。

public void generatePermutations(String s, String permutation) {
    if (s.isEmpty()) {
        System.out.println(permutation); // 输出当前排列
        return;
    }
    for (int i = 0; i < s.length(); i++) {
        char ch = s.charAt(i);
        String rest = s.substring(0, i) + s.substring(i + 1); // 移除当前字符
        generatePermutations(rest, permutation + ch); // 生成剩余字符的排列
    }
}

String str = "abc";
generatePermutations(str, ""); // 调用函数生成所有排列

排列型枚举是一种在一组元素中选择若干个元素按照一定顺序排列的枚举方法。其固定的流程和算法模板可以总结如下：

固定流程

1. 确定问题的解空间： 确定需要进行排列枚举的元素集合，通常是一个数组或集合。

2. 使用递归或迭代方式生成排列： 对于每个可能的元素排列，递归或迭代生成排列，并对每种排列进行处理。

3. 根据问题需求处理排列： 对于每种生成的排列，根据具体问题需求进行处理，例如计算排列的值、检查排列是否满足条件等。

算法模板

下面是一个基于递归的排列型枚举的算法模板：

public void generatePermutations(int[] nums, List<Integer> permutation, boolean[] visited) {
    // 递归终止条件：排列中包含了所有元素
    if (permutation.size() == nums.length) {
        // 处理当前排列，例如输出或其他操作
        System.out.println(permutation);
        return;
    }
    // 递归生成排列
    for (int i = 0; i < nums.length; i++) {
        if (!visited[i]) {
            visited[i] = true; // 标记当前元素已访问
            permutation.add(nums[i]); // 添加当前元素到排列中
            generatePermutations(nums, permutation, visited); // 递归生成剩余元素的排列
            permutation.remove(permutation.size() - 1); // 回溯，移除当前元素
            visited[i] = false; // 恢复当前元素的未访问状态
        }
    }
}

1. generatePermutations 方法接收参数包括原始数组 nums，当前排列 permutation，以及一个标记数组 visited 用于记录元素的访问状态。
2. 当排列中包含了所有元素时，递归终止，处理当前排列。可以根据具体需求进行输出或其他操作。
3. 在每次递归中，遍历原始数组中的所有元素，如果当前元素未被访问过，则将其添加到排列中，并递归生成剩余元素的排列。
4. 在递归返回后，执行回溯操作，将当前元素移除，同时恢复当前元素的未访问状态。
5. 最后，调用函数时传入原始数组、一个空的排列以及一个初始为未访问的标记数组，生成所有符合条件的排列。

例题：全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3]，[1,3,2]，[2,1,3]，[2,3,1]，[3,1,2]，[3,2,1]]

示例 2：

输入：nums = [0,1]
输出：[[0,1]，[1,0]]

示例 3：

输入：nums = [1]
输出：[[1]]

使用模板解决：

我们直接使用排列型枚举的算法模板来解决这个问题。具体步骤如下：

1. 使用递归的方式生成所有可能的排列。
2. 确定排列中的元素包含了数组 nums 中的所有元素。
3. 使用一个标记数组 visited 记录每个元素的访问状态。
4. 根据递归终止条件，在排列中包含了所有元素时，输出当前排列。

代码示例：

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        generatePermutations(nums, new ArrayList<>()， new boolean[nums.length]， result);
        return result;
    }

    private void generatePermutations(int[] nums, List<Integer> permutation, boolean[] visited, List<List<Integer>> result) {
        // 递归终止条件：排列中包含了所有元素
        if (permutation.size() == nums.length) {
            result.add(new ArrayList<>(permutation)); // 将当前排列添加到结果中
            return;
        }
        // 递归生成排列
        for (int i = 0; i < nums.length; i++) {
            if (!visited[i]) {
                visited[i] = true; // 标记当前元素已访问
                permutation.add(nums[i]); // 添加当前元素到排列中
                generatePermutations(nums, permutation, visited, result); // 递归生成剩余元素的排列
                permutation.remove(permutation.size() - 1); // 回溯，移除当前元素
                visited[i] = false; // 恢复当前元素的未访问状态
            }
        }
    }
}

在上面的代码中，permute 方法接收整数数组 nums，返回其所有可能的全排列。通过调用 generatePermutations 方法生成所有排列，并将结果保存在 result 列表中。最后，在 main 方法中调用 permute 方法，并输出所有可能的排列。

指数型枚举

这种枚举法适用于需要枚举所有子集的情况，它的时间复杂度是指数级的。

实现步骤:

• 确定需要枚举的对象(通常是一个集合的所有子集)
• 使用递归或位运算来生成所有子集
• 检查每个子集是否满足要求
• 记录符合要求的子集

例子： 输出数组的所有子序列

使用技巧：

• 使用递归方法生成子序列。
• 对于每个元素，可以选择包含或不包含在子序列中。
• 递归地生成包含当前元素的子序列和不包含当前元素的子序列，直到遍历完整个数组。

public void generateSubsequences(int[] nums, List<Integer> subsequence, int index) {
    if (index == nums.length) {
        System.out.println(subsequence); // 输出当前子序列
        return;
    }
    generateSubsequences(nums, subsequence, index + 1); // 不包含当前元素
    subsequence.add(nums[index]);
    generateSubsequences(nums, subsequence, index + 1); // 包含当前元素
    subsequence.remove(subsequence.size() - 1); // 回溯
}

int[] arr = {1, 2, 3};
generateSubsequences(arr, new ArrayList<>()， 0); // 调用函数生成所有子序列

指数型枚举是一种在每个元素上都有两种选择（选取或不选取）的枚举方法。它通常用于解决需要在多个选项中进行选择的问题，如子集生成、二进制枚举等。以下是指数型枚举的固定流程和算法模板：

固定流程

1. 确定问题的解空间： 确定需要进行指数型枚举的元素集合，通常是一个数组或集合。

2. 使用递归或迭代方式生成所有可能的选择： 对于每个元素，考虑两种选择：选取或不选取。递归或迭代生成所有可能的选择组合。

3. 根据问题需求处理选择： 对于每个生成的选择组合，根据具体问题需求进行处理，例如计算选择的和、检查选择是否满足条件等。

算法模板

以下是一个基于递归的指数型枚举的算法模板：

public void generateSubsets(int[] nums, List<Integer> subset, int index) {
    // 处理当前选择，例如输出或其他操作
    System.out.println(subset);
    // 递归终止条件：已经遍历完所有元素
    if (index == nums.length) {
        return;
    }
    // 选择当前元素
    subset.add(nums[index]);
    generateSubsets(nums, subset, index + 1); // 递归生成包含当前元素的子集
    subset.remove(subset.size() - 1); // 回溯，撤销选择
    // 不选择当前元素
    generateSubsets(nums, subset, index + 1); // 递归生成不包含当前元素的子集
}

// 调用函数生成所有子集
int[] nums = {1, 2, 3};
generateSubsets(nums, new ArrayList<>()， 0);

1. generateSubsets 方法接收参数包括原始数组 nums、当前子集 subset 以及当前遍历的元素索引 index。

2. 处理当前选择，例如输出当前子集。

3. 在递归中，对于当前元素 nums[index]，分两种情况进行递归调用：

   • 选择当前元素：将当前元素添加到子集中，并递归生成包含当前元素的子集。
   • 不选择当前元素：直接递归生成不包含当前元素的子集。

4. 递归终止条件是已经遍历完所有元素，即 index == nums.length。

5. 通过不断选择和不选择，递归地生成所有可能的子集。

例题：递归实现指数型枚举

从 1∼ n个整数中随机选取任意多个，输出所有可能的选择方案。

输入格式：

输入一个整数 n。

输出格式:

每行输出一种方案。
同一行内的数必须升序排列，相邻两个数用恰好 11 个空格隔开。
对于没有选任何数的方案，输出空行。
各行（不同方案）之间的顺序任意。

示例：

输入：3
输出：3
     2
     2 3
     1
     1 3
     1 2
     1 2 3

使用模板解决：

我们可以使用指数型枚举的算法模板来解决这个问题。具体步骤如下：

1. 对于集合中的每个元素，用二进制位表示是否选择该元素。通过枚举二进制数来遍历集合的所有子集。
2. 对于每个生成的子集，输出选择了的元素。

代码示例：

import java.util.*;

public class SubsetGenerator {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(); // 读取输入的整数n
        List<List<Integer>> subsets = generateSubsets(n); // 调用函数生成所有可能的选择方案
        // 遍历所有的选择方案
        for (List<Integer> subset : subsets) {
            if (!subset.isEmpty()) { // 如果当前方案不为空
                for (int i = 0; i < subset.size(); i++) {
                    if (i > 0) {
                        System.out.print(" "); // 输出当前元素之前先输出一个空格
                    }
                    System.out.print(subset.get(i)); // 输出当前元素
                }
                System.out.println(); // 换行
            } else {
                System.out.println(); // 如果当前方案为空，输出一个空行
            }
        }
    }

    // 生成所有可能的选择方案
    public static List<List<Integer>> generateSubsets(int n) {
        List<List<Integer>> subsets = new ArrayList<>(); // 存储所有的选择方案
        // 通过枚举子集的二进制表示来生成所有可能的选择方案
        for (int mask = 0; mask < (1 << n); mask++) {
            List<Integer> subset = new ArrayList<>(); // 当前的选择方案
            // 对于每个子集，判断是否选择了当前元素
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) > 0) { // 如果选择了当前元素
                    subset.add(i + 1); // 将当前元素加入到选择方案中
                }
            }
            subsets.add(subset); // 将当前选择方案加入到结果集中
        }
        return subsets; // 返回所有的选择方案
    }
}

在上面的代码中，我们通过枚举子集的二进制表示来生成所有可能的选择方案。对于每个子集，我们将其转换为对应的整数，并输出选择了的元素。最终得到的结果即为从 1 到 n 个整数中随机选取任意多个的所有可能的选择方案。

枚举例题：24点游戏

题目描述:

给定一个长度为4的整数数组 cards 。你有 4 张卡片，每张卡片上都包含一个范围在 [1,9] 的数字。您应该使用运算符 ['+'， '-'， '*'， '/'] 和括号 '(' 和 ')' 将这些卡片上的数字排列成数学表达式，以获得值24。

你须遵守以下规则:

• 除法运算符

  '/'
  

  表示实数除法，而不是整数除法。

  • 例如， 4 /(1 - 2 / 3)= 4 /(1 / 3)= 12 。

• 每个运算都在两个数字之间。特别是，不能使用

  “-”
  

  作为一元运算符。

  • 例如，如果 cards =[1,1,1,1] ，则表达式 “-1 -1 -1 -1” 是 不允许 的。

• 你不能把数字串在一起

  • 例如，如果 cards =[1,2,1,2] ，则表达式 “12 + 12” 无效。

如果可以得到这样的表达式，其计算结果为 24 ，则返回 true ，否则返回 false 。

示例 1:

输入: cards = [4, 1, 8, 7]
输出: true
解释: (8-4) * (7-1) = 24

示例 2:

输入: cards = [1, 2, 1, 2]
输出: false

运行限制:

最大运行时间：1s
最大运行内存: 128M

题目解析：

我们可以通过枚举所有可能的运算表达式来判断是否可以得到结果为24的表达式。

以下是一个使用枚举法的解题思路：

1. 枚举所有可能的排列和组合： 首先，我们可以枚举所有可能的排列和组合，即将4个数字进行排列和组合，得到不同的数学表达式。

2. 枚举所有可能的运算符排列： 对于每个数字排列，我们需要枚举所有可能的运算符排列，包括 +、-、*、/，以及括号的位置。

3. 计算表达式的值： 对于每个得到的表达式，我们计算其值并检查是否等于24。

boolean judgePoint24(int[] cards) {
    List<Double> nums = new ArrayList<>();
    for (int card : cards) {
        nums.add((double) card);
    }
    return dfs(nums);
}

boolean dfs(List<Double> nums) {
    if (nums.size() == 1) {
        // 比较两个浮点数之间是否非常接近
        return Math.abs(nums.get(0) - 24) < 1e-6; // 判断是否等于24
    }
    for (int i = 0; i < nums.size(); i++) {
        for (int j = 0; j < nums.size(); j++) {
            if (i != j) {
                List<Double> next = new ArrayList<>();
                for (int k = 0; k < nums.size(); k++) {
                    if (k != i && k != j) {
                        next.add(nums.get(k));
                    }
                }
                for (int k = 0; k < 4; k++) { // 枚举所有运算符
                    if (k < 2 && j > i) {
                        continue; // 加法和乘法交换律，避免重复计算
                    }
                    if (k == 0) {
                        next.add(nums.get(i) + nums.get(j)); // 加法
                    } else if (k == 1) {
                        next.add(nums.get(i) * nums.get(j)); // 乘法
                    } else if (k == 2) {
                        next.add(nums.get(i) - nums.get(j)); // 减法
                    } else if (k == 3) {
                        if (Math.abs(nums.get(j)) < 1e-6) {
                            continue; // 除数为0，跳过
                        } else {
                            next.add(nums.get(i) / nums.get(j)); // 除法
                        }
                    }
                    if (dfs(next)) { // 递归计算下一步
                        return true;
                    }
                    next.remove(next.size() - 1); // 回溯
                }
            }
        }
    }
    return false;
}

这段代码使用了深度优先搜索（DFS）来枚举所有可能的计算表达式，逐步计算并判断是否等于24。

之后会详细讲解 DFS 和 BFS 和递归递推，这里理解枚举的思想就行

尺取法

尺取法是一种常用的优化技巧，特别适用于解决序列的区间问题。它的操作简单，易于编程，是一种线性高效的算法。

核心思想：

尺取法的核心思想是维护一个区间（左指针L，右指针R），其中L为起点，R为终点，该区间是序列内以L为起点的最短合法区间。关键在于R随着L的增大而增大。通过不断枚举L，同时求解相应的R，可以高效地解决问题。

实现步骤：

1. 初始化左指针L和右指针R。
2. 不断移动L指针，同时更新R指针，直到R随着L的增大而增大，或满足特定条件停止。
3. 在每次移动L指针的过程中，根据题目要求更新答案或记录结果。
4. 重复步骤2和步骤3，直到L超过R或满足其他特定情况（根据题目而定）。

示例应用：

尺取法广泛应用于需要寻找满足某种条件的连续子序列的问题，例如：

• 最短连续子数组满足条件
• 最长连续子数组满足条件
• 连续子数组和满足特定值等

通过维护两个指针，即左指针L和右指针R，在保持算法简洁的同时，提高解题效率。

根据问题的不同，尺取法可以分为以下几种常见分类，并且每种分类都有其特定的使用技巧：

快慢指针

• 特点： 一快一慢两个指针同时从同一方向（通常是数组或链表的起始位置）移动，快指针移动速度快于慢指针，两指针之间的间隔固定。
• 应用场景： 用于解决链表中的环检测、链表中的中点查找等问题。
• 使用技巧：
  • 慢指针用于遍历链表，快指针用于在特定条件下移动。
  • 可以通过设置不同的间隔来调整算法的效率。

例题：链表的中间结点

给你单链表的头结点 head ，请你找出并返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 1：

输入：head = [1,2,3,4,5]
输出：[3,4,5]
解释：链表只有一个中间结点，值为 3 。

示例 2：

输入：head = [1,2,3,4,5,6]
输出：[4,5,6]
解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。

解题思路：
要找到单链表的中间结点，可以使用快慢指针的方法。快慢指针的核心思想是同时从链表的起始位置出发，慢指针每次移动一步，快指针每次移动两步，当快指针到达链表末尾时，慢指针刚好处于链表的中间位置。

具体步骤如下：

1. 初始化快指针和慢指针，都指向链表的头结点。
2. 使用循环遍历链表，快指针每次移动两步，慢指针每次移动一步，直到快指针到达链表的末尾（即快指针的下一个节点为null）。
3. 当快指针到达末尾时，慢指针所指的节点就是链表的中间结点。

如果链表中的结点数为偶数，则返回第二个中间结点。

通过两个指针以不同的步长同时移动，从而找到问题的解，这种方法在查找链表中的中间结点、环检测等问题中被广泛应用。

代码示例：

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        
        while (fast != null && fast.next != null) {
            fast = fast.next.next; // 快指针每次移动两步
            slow  = slow.next;
        }
        // 当快指针到最后的时候，慢指针就到了中间
        return slow;
    }
}

对撞指针

• 特点： 两个指针分别从数组或链表的两端出发，向中间移动，直到两指针相遇或交错。
• 应用场景： 用于解决数组或链表中的查找问题，例如有序数组的两数之和、回文串判断等。
• 使用技巧：
  • 适用于对称性较强的问题。
  • 在移动指针时，根据题目要求调整移动的条件和步长。

例题：两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15]， target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4]， target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3]， target = 6
输出：[0,1]

实例代码：

由于题目给的数组不是有序的，所以用哈希会更快一点，这里主要理解对撞指针

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // 复制并排序原始数组
        int[] sortedNums = Arrays.copyOf(nums, nums.length);
        Arrays.sort(sortedNums);

        // 定义左指针和右指针
        int left = 0, right = sortedNums.length - 1;

        // 循环直到左指针超过右指针
        while (left < right) {
            // 计算当前左右指针位置的两个数的和
            int sum = sortedNums[left] + sortedNums[right];

            // 如果和等于目标值，则在原始数组中查找对应的下标
            if (sum == target) {
                // 查找第一个数的下标
                int index1 = -1;
                for (int i = 0; i < nums.length; i++) {
                    if (nums[i] == sortedNums[left]) {
                        index1 = i;
                        break;
                    }
                }
                // 查找第二个数的下标
                int index2 = -1;
                for (int i = nums.length - 1; i >= 0; i--) {
                    if (nums[i] == sortedNums[right]) {
                        index2 = i;
                        break;
                    }
                }
                // 返回结果
                return new int[] {index1, index2};
            } else if (sum < target) { // 如果和小于目标值，则将左指针向右移动一位
                left++;
            } else { // 如果和大于目标值，则将右指针向左移动一位
                right--;
            }
        }

        // 如果未找到符合条件的解，则返回空数组
        return new int[0];
    }
}

滑动窗口

滑动窗口是一种常用的技巧,它可以高效地解决很多涉及到连续子序列或子数组的问题。

核心思想:

维护一个窗口,该窗口包含了需要处理的元素序列的一部分。随着遍历的进行,窗口会不断向右滑动,并根据需要动态地增加或缩小窗口的大小。

一般步骤如下:

1. 初始化一个窗口,该窗口包含了需要处理的序列的一部分元素。
2. 移动窗口的两端(左端或右端),使得窗口内的元素满足某种条件或特征。
3. 记录满足条件的窗口状态或结果。
4. 重复步骤 2 和 3,直到窗口遍历完整个序列。

优势:

1. 避免了暴力解法中重复计算的问题。通过维护一个窗口,只需要在窗口移动时进行局部计算和更新,从而减少了不必要的重复计算。
2. 充分利用了数据的局部性特点。滑动窗口算法只需要关注窗口内的元素,而不需要考虑整个序列,从而降低了时间和空间复杂度。
3. 简化了问题的求解思路。对于一些涉及连续子序列或子数组的问题,利用滑动窗口可以将问题转化为更容易处理的形式。

滑动窗口经常用于以下几种类型的问题:

1. 子串问题:例如找出给定字符串中不含重复字符的最长子串长度等。
2. 子数组问题:例如找出给定数组中和为特定值的最长子数组长度等。
3. 序列问题:例如求解最长递增子序列等。

使用技巧：

1. 确定窗口的两端
   • 确定窗口的左右两端的含义,即它们代表什么。通常左端表示子序列/子数组的开始位置,右端表示结束位置。
2. 确定窗口大小的更新条件
   • 根据具体问题,确定窗口大小变化的条件。例如,当窗口内元素满足某种条件时,需要扩大窗口;当窗口内元素不满足条件时,需要缩小窗口。
3. 使用双指针来表示窗口
   • 通常使用两个指针 left 和 right 来表示窗口的左右边界。根据窗口大小更新条件,不断移动这两个指针来扩大或缩小窗口。
4. 使用数据结构来存储窗口内元素
   • 根据具体问题,可以使用不同的数据结构(如队列、哈希表等)来存储和维护窗口内的元素,以便高效地进行查找、插入和删除操作。
5. 记录满足条件的结果
   • 在移动窗口的过程中,需要记录满足条件的结果,如最长子串长度、子数组之和等。
6. 边界条件处理
   • 在移动窗口时,需要特别注意处理好边界条件,如窗口左端或右端到达序列边界时的处理。

例题：滑动子数组的美丽值

给你一个长度为 n 的整数数组 nums ，请你求出每个长度为 k 的子数组的 美丽值 。

一个子数组的 美丽值 定义为：如果子数组中第 x 小整数 是 负数 ，那么美丽值为第 x 小的数，否则美丽值为 0 。

请你返回一个包含 n - k + 1 个整数的数组，依次 表示数组中从第一个下标开始，每个长度为 k 的子数组的 美丽值 。

• 子数组指的是数组中一段连续 非空 的元素序列。

示例 1：

输入：nums = [1,-1,-3,-2,3]， k = 3, x = 2
输出：[-1,-2,-2]
解释：总共有 3 个 k = 3 的子数组。
第一个子数组是 [1, -1, -3] ，第二小的数是负数 -1 。
第二个子数组是 [-1, -3, -2] ，第二小的数是负数 -2 。
第三个子数组是 [-3, -2, 3] ，第二小的数是负数 -2 。

示例 2：

输入：nums = [-1,-2,-3,-4,-5]， k = 2, x = 2
输出：[-1,-2,-3,-4]
解释：总共有 4 个 k = 2 的子数组。
[-1, -2] 中第二小的数是负数 -1 。
[-2, -3] 中第二小的数是负数 -2 。
[-3, -4] 中第二小的数是负数 -3 。
[-4, -5] 中第二小的数是负数 -4 。

示例 3：

输入：nums = [-3,1,2,-3,0,-3]， k = 2, x = 1
输出：[-3,0,-3,-3,-3]
解释：总共有 5 个 k = 2 的子数组。
[-3, 1] 中最小的数是负数 -3 。
[1, 2] 中最小的数不是负数，所以美丽值为 0 。
[2, -3] 中最小的数是负数 -3 。
[-3, 0] 中最小的数是负数 -3 。
[0, -3] 中最小的数是负数 -3 。

题解：

使用有序哈希表。具体思路如下:

1. 使用一个有序哈希表(TreeMap)来存储数组中的元素及其索引列表。
2. 初始化第一个长度为k的子数组，将其所有元素及其索引存入有序哈希表中。
3. 计算第一个子数组的美丽值，并存入结果数组中。
4. 对于后续的每个子数组，我们只需要从有序哈希表中移除旧元素及其索引，添加新元素及其索引。
5. 在有序哈希表中，我们可以很方便地找到第x小的元素，从而计算出当前子数组的美丽值。
6. 重复步骤4-5，直到遍历完整个数组。

核心思路是:

1. 我们使用一个TreeMap来存储数组中的元素及其索引列表。TreeMap会自动按照键(元素值)的大小进行排序。
2. 在初始化第一个窗口时，我们将所有元素及其索引存入TreeMap中。
3. 在移动窗口时，我们从TreeMap中移除旧元素及其索引，添加新元素及其索引。
4. 编写了一个辅助函数getBeauty来计算美丽值。该函数遍历TreeMap中的条目，累加每个元素的索引列表大小。当累加的大小达到或超过x时，就找到了第x小的元素，返回它的值(如果是负数)或0(如果是非负数)。

这种解法的时间复杂度为O(n * k * log k)。其中，移动窗口的操作需要O(log k)的时间复杂度，因为需要在TreeMap中插入和删除元素。而获取第x小的元素的时间复杂度为O(k * log k)，因为需要遍历TreeMap中的所有条目。

相比基于排序的解法，这种解法避免了每次都完全排序的开销，效率会有所提升。同时，它也比使用优先队列的解法更加简洁直观。

示例代码：

class Solution {

    public int[] getSubarrayBeauty(int[] nums, int k, int x) {
        int n = nums.length;
        int[] result = new int[n - k + 1]; // 结果数组，存储每个长度为k的子数组的美丽值
        TreeMap<Integer, List<Integer>> map = new TreeMap<>(); // 有序哈希表，存储元素值及其索引列表

        // 初始化第一个长度为k的窗口
        for (int i = 0; i < k; i++) {
            // 如果元素第一次出现，则创建一个新的索引列表
            map.computeIfAbsent(nums[i]， v -> new ArrayList<>()).add(i);
        }

        // 计算第一个窗口的美丽值
        result[0] = getBeauty(map, x);

        for (int i = k; i < n; i++) {
            // 移除窗口左侧的旧元素
            List<Integer> indices = map.get(nums[i - k]); // 获取旧元素的索引列表
            indices.remove(indices.size() - 1); // 移除最后一个索引(即窗口左侧的索引)
            if (indices.isEmpty()) {
                // 如果索引列表为空，则从哈希表中移除该元素
                map.remove(nums[i - k]);
            }

            // 添加窗口右侧的新元素
            map.computeIfAbsent(nums[i]， v -> new ArrayList<>()).add(i);

            // 计算当前窗口的美丽值
            result[i - k + 1] = getBeauty(map, x);
        }

        return result;
    }

    private int getBeauty(TreeMap<Integer, List<Integer>> map, int x) {
        int count = 0;
        // 遍历有序哈希表中的条目
        for (Map.Entry<Integer, List<Integer>> entry : map.entrySet()) {
            count += entry.getValue().size(); // 累加当前元素的索引列表大小
            if (count >= x) {
                // 如果累加的大小达到或超过x,说明找到了第x小的元素
                return entry.getKey() < 0 ? entry.getKey() : 0;
            }
        }
        // 如果没有找到第x小的负数，则返回0
        return 0;
    }
}

1. 初始化第一个长度为k的窗口:

   • 我们使用一个for循环遍历数组的前k个元素。
   • 对于每个元素，我们检查它是否第一次出现在有序哈希表中。
   • 如果是第一次出现，我们创建一个新的索引列表，并将当前元素的索引添加到该列表中。
   • 如果元素已经存在，我们直接将当前索引添加到对应的索引列表中。

2. 移动窗口:

   • 我们使用另一个for循环来移动窗口，遍历数组中从第k个元素开始的所有元素。
   • 对于每个新的窗口位置，我们首先需要移除旧元素及其索引。
   • 我们从有序哈希表中获取旧元素的索引列表。
   • 我们移除该索引列表中的最后一个元素，因为它对应着窗口左侧被移除的元素。
   • 如果索引列表变为空，我们从有序哈希表中移除该元素。
   • 然后，我们将新元素及其索引添加到有序哈希表中。
   • 最后，我们调用getBeauty函数计算当前窗口的美丽值，并将结果存储到结果数组中。

3. 计算美丽值:

   • getBeauty函数接受有序哈希表和目标位置x作为参数。
   • 我们使用一个变量count来累加每个元素的索引列表大小。
   • 我们遍历有序哈希表中的所有条目。
   • 对于每个条目，我们将其索引列表的大小累加到count中。
   • 如果count达到或超过x,说明我们找到了第x小的元素。
   • 我们返回该元素的值(如果是负数)或0(如果是非负数)。
   • 如果遍历完整个有序哈希表还没有找到第x小的负数，我们返回0。

这种基于有序哈希表的解法充分利用了TreeMap的有序性质，可以高效地在移动窗口时维护元素的顺序。同时，通过存储索引列表，我们可以在常数时间内移除或添加元素，避免了重复的索引查找操作。