• 1. 二分查找
• 2. 搜索插入位置
  • 思路一：暴力解法
  • 思路二：二分查找法
• 3. 在排序数组中查找元素的第一个和最后一个位置
• 4. x 的平方根
• 5. 有效的完全平方数
• 6. 移除元素
  • 思路一：暴力解法
  • 思路二：双指针法
• 7. 删除有序数组中的重复项
• 8. 移动零
• 9. 比较含退格的字符串
  • 思路一：栈
  • 思路二：双指针
• 10. 有序数组的平方
  • 思路一：暴力解法
  • 思路二：双指针法
• 11. 长度最小的子数组
  • 思路一：暴力解法
  • 思路二：滑动窗口法
  • 框架解题代码如下
• 12. 水果成篮
• 13. 最小覆盖子串
• 14. 字符串的排列
  • 思路一：暴力解法
  • 思路二：滑动窗口（模板解）
• 15. 找到字符串中所有的字母异位词
  • 哈希表+滑动窗口解题
• 16. 无重复字符的最长子串
• 17. 螺旋矩阵II

1. 二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9

输出: 4

解释: 9 出现在 nums 中并且下标为 4

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2

输出: -1

解释: 2 不存在 nums 中因此返回 -1

提示：

1. 你可以假设 nums 中的所有元素是不重复的。
2. n 将在 [1, 10000]之间。
3. nums 的每个元素都将在 [-9999, 9999]之间。

解题思路如下 ：力扣链接 (opens new window)

1. 初始化：设置两个指针，分别指向数组的开头（left）和结尾（right）。
2. 迭代查找：
   • 在每次迭代中，计算中间位置 mid。
   • 比较中间位置的元素与目标值 target
     • 如果中间元素等于 target，则找到目标值，返回其索引。
     • 如果中间元素大于 target，则调整右指针 right 到 mid - 1，因为目标值在左半部分。
     • 如果中间元素小于 target，则调整左指针 left 到 mid + 1，因为目标值在右半部分。
3. 未找到情况：
   • 如果左指针 left 超过右指针 right，表示整个数组已被搜索过，但未找到目标值，此时返回 -1。

例如在数组：1,2,3,4,7,9,10中查找元素2，如图所示：

二分查找跳出while的条件为什么是left <= right，而不是left < right ?

• 包含边界元素：当 left 和 right 指向同一个元素时，使用 left <= right 保证这个元素在搜索范围内，从而不会错过它。
• 处理单元素数组：如果数组只有一个元素，left 和 right 会指向同一个位置。使用 left <= right 确保循环至少执行一次，以检查这个唯一的元素。

**时间复杂度分析：**二分查找的时间复杂度是 O(logn)

• 假设数组的长度是 n。在第一次迭代后，搜索空间减少为 n/2；第二次迭代后，减少为 n/4；依此类推，直到搜索空间减少到只剩一个元素或没有元素。
• 因此，迭代的次数是 O(log n)。这是因为 n 被反复除以 2 直到它变成 1，这需要 log2 n 步。

解题代码如下

class Solution {
    public int search(int[] nums, int target) {
        // 初始化左右指针
        int left = 0;
        int right = nums.length - 1;

        // 当左指针不超过右指针时循环
        while (left <= right) {
            // 计算中间位置
            int mid = (left + right) >>> 1;

            // 比较中间位置的元素与目标值
            if (nums[mid] > target) {
                // 如果中间元素大于目标值，调整右指针，搜索左半部分
                right = mid - 1;
            } else if (nums[mid] < target) {
                // 如果中间元素小于目标值，调整左指针，搜索右半部分
                left = mid + 1;
            } else {
                // 如果中间元素等于目标值，返回该位置的索引
                return mid;
            }
        }
        // 如果未找到目标值，返回-1
        return -1;
    }
}

2. 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

输入: nums = [1,3,5,6], target = 5

输出: 2

示例 2:

输入: nums = [1,3,5,6], target = 2

输出: 1

示例 3:

输入: nums = [1,3,5,6], target = 7

输出: 4

提示:

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums 为 无重复元素 的 升序 排列数组
• -104 <= target <= 104

解题思路如下：力扣链接 (opens new window)

思路一：暴力解法

1. 遍历数组：从数组的第一个元素开始，向后遍历。这个过程中我们会考虑数组中的每个元素与目标值的关系。
2. 检查四种情况：
   • 目标值在数组所有元素之前：如果数组的第一个元素就大于目标值，那么目标值应该被插入在数组的起始位置，索引为 0。
   • 目标值等于数组中某一个元素：如果在遍历过程中找到一个元素与目标值相等，返回该元素的索引。
   • 目标值插入数组中的位置：如果找到一个元素大于目标值，那么目标值应该被插入在这个元素之前的位置，返回当前元素的索引。
   • 目标值在数组所有元素之后：如果遍历完整个数组都没有找到大于或等于目标值的元素，这意味着目标值应该被插入数组末尾，返回数组长度。

• 时间复杂度是 O(n)。代码中有一个循环，它遍历了数组 nums 的每个元素。在最坏的情况下（即目标值大于数组中所有元素或数组为空），循环会执行 n 次，其中 n 是数组 nums 的长度。

class Solution {
    public int searchInsert(int[] nums, int target) {
        // 遍历数组
        for (int i = 0; i < nums.length; i++) {
            // 检查目标值与数组元素的关系
            if (nums[i] >= target) {
                // 找到第一个大于或等于目标值的元素，返回其索引
                return i;
            }
        }
        // 如果遍历结束都没有找到，目标值应插入数组末尾
        return nums.length;
    }
}

思路二：二分查找法

1. 初始化变量：定义数组长度 n，初始化左指针 left 为 0，右指针 right 为 n-1。
2. 开始循环：当左指针不大于右指针时，计算中间位置 mid。
3. 比较和移动 ：
   • 如果 nums[mid] == target，直接返回 mid，找到了目标值。
   • 如果 nums[mid] > target，则目标值在左侧区域，移动右指针 right 到 middle - 1。
   • 如果 nums[mid] < target，则目标值在右侧区域，移动左指针 left 到 middle + 1。
4. 未找到目标值：循环结束，如果没有找到目标值，则根据二分查找的性质，left 指针指向的位置是第一个大于目标值的元素位置，或者所有元素都小于目标值，left 指向数组长度，即新元素应该插入的位置。

时间复杂度：由于每次迭代都减少一半的搜索区间，所以，算法的时间复杂度为 O(log n)。

class Solution {
    public int searchInsert(int[] nums, int target) {
        int n = nums.length; // 数组长度
        int left = 0; // 初始化左指针
        int right = n - 1; // 初始化右指针
        
        // 当左指针小于等于右指针时进行循环
        while (left <= right) {
            // 计算中间指针的位置
            int mid = (right + left) / 2;
            
            // 如果中间的数刚好是目标值，则直接返回中间位置
            if (nums[mid] == target) {
                return mid;
            } else if (nums[middle] > target) { // 如果中间的数大于目标值，则目标值在左侧区域
                right = mid - 1;
            } else { // 如果中间的数小于目标值，则目标值在右侧区域
                left = mid + 1;
            }
        }
        
        // 循环结束，如果没有找到目标值，则目标值应该插入的位置是左指针的位置
        // 此时，left指针指向的是第一个大于目标值的元素位置，
        // 或者所有元素都小于目标值，left指向的是数组长度，即新元素应该插入的位置
        return left;
    }
}

3. 在排序数组中查找元素的第一个和最后一个位置

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8

输出：[3,4]

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6

输出：[-1,-1]

示例 3：

输入：nums = [], target = 0

输出：[-1,-1]

提示：

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109
• nums 是一个非递减数组
• -109 <= target <= 109

解题思路如下：力扣链接 (opens new window)

1. 查找开始位置：
   • 使用标准的二分查找。
   • 当找到一个等于目标值的元素时，继续向左侧探索，以确定是否有相同的元素存在，即继续缩小右边界。
2. 查找结束位置：
   • 同样使用二分查找，但当找到目标值时，向右侧探索。
   • 当找到一个等于目标值的元素时，继续向右侧探索，以确定是否有相同的元素存在，即继续缩小左边界。
3. 注意处理边界条件：
   • 如果数组为空或者从未找到目标值，则返回[-1, -1]。
   • 确保在查找过程中不会越过数组的边界。

• 时间复杂度：两次二分查找是连续的而不是嵌套的，因此总时间复杂度仍然是O(log n) + O(log n) = O(log n)

解题代码如下

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] result = new int[2]; // 结果数组，存放开始和结束位置
        result[0] = findFirst(nums, target); // 查找开始位置
        result[1] = findLast(nums, target); // 查找结束位置
        return result;
    }

    // 二分查找，寻找开始位置
    private int findFirst(int[] nums, int target) {
        int index = -1; // 默认值为-1，表示未找到
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {	
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target) { // 即使相等找到了目标值也不会退出循环
                right = mid - 1; // 继续在左区间寻找
            } else {
                left = mid + 1;
            }
            if (nums[mid] == target) index = mid; // 更新找到的位置
        }
        return index;
    }

    // 二分查找，寻找结束位置
    private int findLast(int[] nums, int target) {
        int index = -1; // 默认值为-1，表示未找到
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {	
            int mid = left + (right - left) / 2;
            if (nums[mid] <= target) { // 即使相等找到了目标值也不会退出循环，
                left = mid + 1; // 继续在右区间寻找
            } else {
                right = mid - 1;
            }
            if (nums[mid] == target) index = mid; // 更新找到的位置
        }
        return index;
    }
}

4. x 的平方根

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1：

输入：x = 4

输出：2

示例 2：

输入：x = 8

输出：2

解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

提示：

• 0 <= x <= 231 - 1

解题思路如下：力扣链接 (opens new window)

为了计算一个非负整数x的算术平方根并且只保留整数部分，我们可以使用二分查找算法。由于平方根函数是单调递增的，我们可以在一个有序的集合（从0到x）中应用二分查找来寻找平方根的整数部分。

1. 初始化边界：设置左边界left为0，右边界right为x。平方根肯定在这个范围内。
2. 二分查找：当left小于等于right时，进行以下操作：
   • 计算中点mid作为候选的平方根。
   • 计算mid * mid并与x比较：
     • 如果mid * mid小于等于x，那么mid可能是平方根的整数部分，或者更大的数可能是平方根，所以移动左边界left到mid + 1。
     • 如果mid * mid大于x，说明mid太大了，我们需要一个更小的数作为候选，所以移动右边界right到mid - 1。
     • 如果相等，找到了精确的平方根
3. 循环结束：当左边界大于右边界时，循环结束。left将指向第一个大于平方根整数部分的数，而right将指向最后一个小于或等于平方根整数部分的数。由于我们需要返回的是整数部分，所以应该返回right。此时right就是最接近且不大于实际平方根的整数值。

在这个平方根算法中，我们将变量定义为long类型是为了防止在计算过程中发生整型溢出。

当x接近int类型的最大值时，假设我们正在寻找一个大数的平方根，中间值mid本身可能不会超过int的范围，但是mid * mid很可能超过。

• 时间复杂度为O(log n)，二分查找的每次迭代都是对区间大小进行一次对半划分。

解题代码如下

class Solution {
    public int mySqrt(int x) {
        // 定义搜索范围
        long left = 0;
        long right = x;
        
        // 二分查找
        while (left <= right) {
            long mid = left + (right - left) / 2;
            long square = mid * mid;
            
            // 检查mid的平方与x的关系
            if (square == x) {
                return (int)mid; // 找到精确的平方根
            } else if (square < x) {
                left = mid + 1; // 增加下界
            } else {
                right = mid - 1; // 减少上界
            }
        }
        
        // 返回整数部分，因为循环结束时left是大于right的，
        // 所以right是最后一个满足square <= x的数
        return (int)right;
    }
}

5. 有效的完全平方数

给你一个正整数 num 。如果 num 是一个完全平方数，则返回 true ，否则返回 false 。

完全平方数 是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。

不能使用任何内置的库函数，如 sqrt 。

示例 1：

输入：num = 16

输出：true

解释：返回 true ，因为 4 * 4 = 16 且 4 是一个整数。

示例 2：

输入：num = 14

输出：false

解释：返回 false ，因为 3.742 * 3.742 = 14 但 3.742 不是一个整数。

提示：

• 1 <= num <= 231 - 1

解题思路如下：力扣链接 (opens new window)

1. 设置边界：由于完全平方数的范围从1到num，我们可以将二分查找的左边界设置为1，右边界设置为num。对于小于2的数字，我们可以直接判断它们是否是完全平方数，1和0都视为完全平方数。
2. 二分查找：：我们知道任何数的平方根最多不会超过它的一半（除了1和2），所以我们设置初始的二分查找范围从1到num/2。然后执行标准的二分查找
   • 计算中间值mid，并计算mid的平方。
   • 如果mid的平方正好等于num，那么num是完全平方数，返回true。
   • 如果mid的平方小于num，那么需要在更大的范围内查找，移动左边界。
   • 如果mid的平方大于num，那么需要在更小的范围内查找，移动右边界。
3. 检查结果：如果循环结束还没有找到满足条件的mid，说明num不是完全平方数，返回false。

• 时间复杂度是O(log n)，因为每次迭代，二分查找都会将搜索区间的大小减半。

解题代码如下

class Solution {
    public boolean isPerfectSquare(int num) {
        if (num < 2) {
            return true; // 如果数字小于2，那么它一定是完全平方数（1或0）
        }
        
        long left = 1, right = num / 2; // 定义搜索范围为1到num/2
        while (left <= right) {
            long mid = left + (right - left) / 2; // 计算中间值，使用long防止溢出
            long square = mid * mid; // 计算中间值的平方
            
            if (square == num) {
                return true; // 如果中间值的平方正好等于num，说明找到了完全平方数
            } else if (square < num) {
                left = mid + 1; // 如果中间值的平方小于num，说明完全平方数在右侧
            } else {
                right = mid - 1; // 如果中间值的平方大于num，说明完全平方数在左侧
            }
        }
        
        return false; // 如果循环结束还没有找到，说明num不是完全平方数
    }
}

6. 移除元素

给你一个数组 nums 和一个值 val，你需要 原地 (opens new window) 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 (opens new window)修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1：

输入：nums = [3,2,2,3], val = 3

输出：2, nums = [2,2]

解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。

例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。

示例 2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2

输出：5, nums = [0,1,3,0,4]

解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

提示：

• 0 <= nums.length <= 100
• 0 <= nums[i] <= 50
• 0 <= val <= 100

解题思路如下：力扣链接 (opens new window)

思路一：暴力解法

1. 遍历数组中的每个元素。
2. 当找到一个与目标值 val 相等的元素时，将该位置以后的所有元素向前移动一位。
3. 因为数组的大小减少了，所以减小数组大小计数，并将索引 i 向后移动一位以重新检查新移动到这个位置的元素。
4. 最后返回处理后数组的新长度

• 时间复杂度为 O(n^2)，因为在最坏的情况下，对于每个元素，你可能需要移动数组中几乎所有的其他元素。
• 空间复杂度是 O(1)，因为只使用了常量额外空间。

class Solution {
    public int removeElement(int[] nums, int val) {
        int size = nums.length;
        for (int i = 0; i < size; i++) {
            if (nums[i] == val) { // 检查当前元素是否为需要移除的元素
                for (int j = i + 1; j < size; j++) {
		    // j-1 就是当前 i == val 的位置，需要覆盖掉这个要被移除的元素
                    nums[j - 1] = nums[j]; // 将后续元素向前移动一位
                }
                i--; // 更新索引以重新检查新移动到当前位置的元素
                size--; // 数组大小减少
            }
        }
        return size; // 返回新的数组大小
    }
}

思路二：双指针法

1. 初始化两个指针：slowIndex（慢指针）和 fastIndex（快指针）。慢指针表示处理后数组的长度，快指针用于遍历数组。
2. 遍历数组。对于每个元素，检查它是否等于 val。
3. 如果当前元素不等于 val，则将它赋值给 slowIndex 指向的位置，并将 slowIndex 向前移动一位。
4. 继续这个过程，直到数组遍历完成。
5. 返回 slowIndex，这是数组中不包含 val 之后的新长度。

• 时间复杂度为 O(n)，因为数组只需要遍历一次。
• 空间复杂度为 O(1)，没有使用额外的存储空间。

class Solution {
    public int removeElement(int[] nums, int val) {
        int slowIndex = 0; // 慢指针
        for (int fastIndex = 0; fastIndex < nums.length; fastIndex++) { // 快指针遍历数组
            if (val != nums[fastIndex]) { // 如果快指针指向的元素不是要移除的元素
                nums[slowIndex] = nums[fastIndex]; // 将其赋值给慢指针指向的位置
                slowIndex++; // 慢指针向前移动一位
            }
        }
        return slowIndex; // 返回新的数组长度
    }
}

7. 删除有序数组中的重复项

给你一个 非严格递增排列 的数组 nums ，请你原地 (opens new window) 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：

• 更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
• 返回 k 。

示例 1：

输入：nums = [1,1,2]

输出：2, nums = [1,2,_]

解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例 2：

输入：nums = [0,0,1,1,1,2,2,3,3,4]

输出：5, nums = [0,1,2,3,4]

解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

提示：

• 1 <= nums.length <= 3 * 104
• -104 <= nums[i] <= 104
• nums 已按 非严格递增 排列

解题思路如下：力扣链接 (opens new window)

这个问题是数组操作中的经典问题，题目指出数组是非严格递增排列的，我们可以断定所有的重复元素一定是连续的。可以使用双指针技术高效解决。

1. 初始化两个指针：一个快指针fast和一个慢指针slow。fast指针用于遍历数组，slow指针用于指向下一个应该放置的元素位置。
2. 遍历数组：使用快指针fast遍历数组，比较当前元素与前一个元素是否相同。
   • 如果相同，则fast指针继续前进，跳过重复项。
   • 如果不同，则将fast指针指向的元素复制到slow指针的位置，然后slow指针前进一位。
3. 更新数组：通过上述步骤，所有不重复的元素都被移动到了数组的前部分。
4. 返回结果：最后，slow指针的位置就是新的数组长度，因为它指向了应该放置下一个新元素的位置。

• 时间复杂度是O(n)，因为它需要遍历一次数组。空间复杂度是O(1)，因为它只使用了常数级别的额外空间。

解题示例如下

class Solution {
    public int removeDuplicates(int[] nums) {
        // 边界条件，如果数组长度为0或1，则无需处理
        if (nums.length <= 1) {
            return nums.length;
        }

        // 初始化两个指针
        int slow = 1; // 从第二个元素开始，因为第一个元素肯定保留
        for (int fast = 1; fast < nums.length; fast++) {
            // 当前元素与前一个元素不同时，复制元素到slow指针的位置，并移动slow
            if (nums[fast] != nums[fast - 1]) {
                nums[slow] = nums[fast];
                slow++;
            }
        }

        // 返回新的长度，即slow指针的位置
        return slow;
    }
}

8. 移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]

输出: [1,3,12,0,0]

示例 2:

输入: nums = [0]

输出: [0]

提示:

• 1 <= nums.length <= 104
• -231 <= nums[i] <= 231 - 1

解题思路如下：力扣链接 (opens new window)

这个问题也可以用双指针方法来解决。核心思想是通过一个快指针遍历数组，找到非零元素，并用一个慢指针来跟踪非零元素应该被移动到的位置。

1. 初始化两个指针：一个快指针fast用于遍历数组，一个慢指针slow用于跟踪下一个非零元素应该放置的位置。
2. 遍历数组：使用快指针遍历数组。
   • 如果快指针指向的元素不为0，则将其值复制到慢指针的位置，并将慢指针向前移动一位。
   • 如果快指针指向的元素为0，则继续移动快指针，直到找到非零元素。
3. 处理剩余的零：遍历完成后，慢指针及其之后的所有位置都应该填充0。
4. 完成操作：此时，所有非零元素都保持了原始相对顺序，并且所有0都被移动到了数组的末尾。

• 时间复杂度为O(n)，因为它需要遍历一次数组，空间复杂度为O(1)，因为它只使用了常数级别的额外空间

解题示例如下

class Solution {
    public void moveZeroes(int[] nums) {
        // 初始化慢指针，用于记录下一个非零元素应该放置的位置
        int slow = 0;
        
        // 快指针遍历数组
        for (int fast = 0; fast < nums.length; fast++) {
            // 如果快指针指向的元素不为0
            if (nums[fast] != 0) {
                // 将其复制到慢指针的位置
                nums[slow] = nums[fast];
                // 移动慢指针
                slow++;
            }
        }
        
        // 填充剩余的位置为0
        for (int i = slow; i < nums.length; i++) {
            nums[i] = 0;
        }
    }
}

9. 比较含退格的字符串

给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。

注意：如果对空文本输入退格字符，文本继续为空。

示例 1：

输入：s = "ab#c", t = "ad#c"

输出：true

解释：s 和 t 都会变成 "ac"。

示例 2：

输入：s = "ab##", t = "c#d#"

输出：true

解释：s 和 t 都会变成 ""。

示例 3：

输入：s = "a#c", t = "b"

输出：false

解释：s 会变成 "c"，但 t 仍然是 "b"。

提示：

• 1 <= s.length, t.length <= 200
• s 和 t 只含有小写字母以及字符 '#'

解题思路如下：力扣链接 (opens new window)

思路一：栈

这个问题可以通过模拟字符串编辑过程来解决。具体来说，我们可以使用栈来模拟每次输入操作。当遇到普通字符时，将其压入栈中；当遇到退格字符'#'时，从栈中弹出一个字符（如果栈不为空）。最后，比较两个字符串处理后的结果是否相同。

1. 初始化两个栈：分别对应s和t字符串，用于存放处理后的结果。

2. 处理字符串s：遍历字符串s中的每个字符：

   • 如果字符不是'#'，则将其压入栈中。

   • 如果字符是'#'且栈不为空，则从栈中弹出一个字符。

   • 循环结束后，栈中的元素顺序即为处理后的字符串。

3. 处理字符串t：同样的方式处理字符串t。

4. 比较两个栈：如果两个栈的大小不同，直接返回false；否则，逐个比较栈中的元素，如果全部相同，则返回true；否则，返回false。

• 时间复杂度为O(n + m)，其中n和m分别为两个字符串的长度，因为我们需要遍历每个字符串一次。
• 空间复杂度为O(n + m)，因为在最坏的情况下，我们可能需要额外的空间来存储所有的字符（如果没有退格发生）

import java.util.Stack;

class Solution {
    public boolean backspaceCompare(String s, String t) {
        // 调用构建函数，构建处理后的字符串
        String finalS = buildString(s);
        String finalT = buildString(t);

        // 比较两个处理后的字符串是否相等
        return finalS.equals(finalT);
    }

    private String buildString(String str) {
        Stack<Character> stack = new Stack<>();
        for (char c : str.toCharArray()) {
            // 如果字符不是'#'，则压入栈中
            if (c != '#') {
                stack.push(c);
            } else if (!stack.isEmpty()) { // 如果是'#'，且栈不为空，则弹出栈顶元素
                stack.pop();
            }
        }

        // 返回栈中的字符序列作为最终结果
        return String.valueOf(stack);
    }
}

思路二：双指针

使用双指针解决这个问题，可以避免使用额外的空间。这种方法的思路是从两个字符串的末尾开始，逐步向前，每次比较两个字符串当前位置的字符是否相同。当遇到'#'时，跳过一定数量的字符。

1. 初始化两个指针：分别指向s和t字符串的末尾。
2. 逆向比较字符：
   • 从后向前遍历字符串，使用两个指针分别指向s和t的当前字符。
   • 如果遇到'#'字符，就需要跳过一定数量的字符。使用一个计数器记录需要跳过的字符数。
   • 移动指针，直到找到下一个需要比较的有效字符。
3. 比较字符：
   • 比较两个字符串中的当前字符是否相同。
   • 如果在任何位置发现字符不相同，或者一个字符串结束而另一个没有结束，返回false。
4. 处理指针：
   • 如果当前字符相同或者都是'#'，则继续向前移动指针。
   • 如果遇到'#'，更新跳过字符的计数，并适当移动指针。
5. 循环直至遍历完毕：重复上述步骤，直到两个指针都移动到各自字符串的开始位置。
6. 返回结果：如果两个字符串都遍历完成，并且所有对应位置的字符都相同，则返回true；否则返回false。

注意事项：当我们在字符串中遇到'#'字符时，它代表的操作是退格，即删除之前的一个字符。在文本编辑器中，如果你输入了一个字符然后按下退格键，那个字符会被删除。如果连续输入了多个退格字符，那么每个退格都会删除之前的一个字符。在这个问题中，我们没有实际的文本编辑器来自动处理退格操作，所以我们需要自己模拟这个过程。

• 时间复杂度为O(n + m)，其中n和m分别为两个字符串的长度。因为我们需要遍历每个字符串一次以处理所有的字符和退格。
• 空间复杂度为O(1)，因为我们只使用了常数级别的额外空间。

class Solution {
    public boolean backspaceCompare(String s, String t) {
        // 初始化两个指针分别指向s和t的末尾
        int i = s.length() - 1, j = t.length() - 1;
        int skipS = 0, skipT = 0; // skipS和skipT用于记录s和t中需要跳过的字符数量

        while (i >= 0 || j >= 0) { // 只要两个字符串有一个没有结束，就继续遍历
            // 寻找s中下一个实际需要比较的字符
            while (i >= 0) {
                if (s.charAt(i) == '#') { // 遇到退格计数器就+1
                    skipS++;
                    i--;
                } else if (skipS > 0) { // 检查是否需要退格
                    skipS--;
                    i--;
                } else {
                    break;
                }
            }
            // 寻找t中下一个实际需要比较的字符
            while (j >= 0) {
                if (t.charAt(j) == '#') { // 遇到退格计数器就+1
                    skipT++;
                    j--;
                } else if (skipT > 0) { // 检查是否需要退格
                    skipT--;
                    j--;
                } else {
                    break;
                }
            }

            // 比较s和t在当前指针位置的字符
            if (i >= 0 && j >= 0 && s.charAt(i) != t.charAt(j)) {
                return false; // 字符不同，返回false
            }
            if ((i >= 0) != (j >= 0)) {
                return false; // 一个字符串结束，另一个没有结束，返回false
            }

            i--; // 移动s的指针
            j--; // 移动t的指针
        }

        return true; // 所有字符都匹配
    }
}

10. 有序数组的平方

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例 1：

输入：nums = [-4,-1,0,3,10]

输出：[0,1,9,16,100]

解释：平方后，数组变为 [16,1,0,9,100]

排序后，数组变为 [0,1,9,16,100]

示例 2：

输入：nums = [-7,-3,2,3,11]

输出：[4,9,9,49,121]

提示：

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums 已按 非递减顺序 排序

解题思路如下：力扣链接 (opens new window)

思路一：暴力解法

1. 遍历数组，将每个元素替换为其平方值。
2. 使用快速排序（如 Arrays.sort() 方法）对数组进行排序。

• 时间复杂度是 O(n) + O(n log n) 也就是O(n log n)
• 数组遍历：遍历数组并计算每个元素的平方。这个操作的时间复杂度是 O(n)，其中 n 是数组 nums 的长度。每个元素都被访问一次。
• 数组排序：使用 Arrays.sort() 对数组进行排序。在大多数情况下，Arrays.sort() 对于基本数据类型使用的是双轴快速排序，其平均时间复杂度是 O(n log n)。

import java.util.Arrays;

class Solution {
    public int[] sortedSquares(int[] nums) {
        // 遍历数组，将每个元素替换为其平方值
        for (int i = 0; i < nums.length; i++) {
            nums[i] = nums[i] * nums[i];
        }
        // 使用快速排序对数组进行排序
        Arrays.sort(nums);
        // 返回处理后的数组
        return nums;
    }
}

思路二：双指针法

题目给出这个数组是有序数组，虽然没有说明是逆序和正序，但是我们可以确定平方的最大值肯定在数组两端，不可能在中间，此时可以考虑双指针法了。

1. 创建一个新数组 result，用于存储排序后的平方数。
2. 设置两个指针，分别指向原数组的开头和结尾。
3. 比较两个指针指向的元素的平方值。
4. 将较大的平方值放在 result 数组的末尾，并移动相应的指针。
5. 重复此过程，直到所有元素都被处理。

• 时间复杂度是 O(n)，这是因为我们只需要一次遍历来处理所有元素
• 遍历数组：虽然使用了两个指针（一个从开始，一个从结束），但实际上每个元素只被访问一次。当两个指针相遇时，遍历结束。因此，遍历整个数组的时间复杂度是 O(n)，其中 n 是数组 A 的长度。
• 填充结果数组：在遍历过程中，我们同时将计算出的平方值填充到结果数组中。这个操作与元素的遍历同步进行，因此不会增加额外的时间复杂度。

class Solution {
    public int[] sortedSquares(int[] nums) {
        int k = nums.length - 1;
        int[] result = new int[nums.length];
        int i = 0, j = nums.length - 1;

        while (i <= j) { // 当i和j相遇时，也需要处理这个元素
            if (nums[i] * nums[i] < nums[j] * nums[j]) {
                result[k--] = nums[j] * nums[j]; // 将较大的平方数放在result数组的末尾
                j--; // 移动右指针
            } else {
                result[k--] = nums[i] * nums[i]; // 同理，处理左指针
                i++; // 移动左指针
            }
        }
        return result;
    }
}

11. 长度最小的子数组

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

解题思路如下：力扣链接 (opens new window)

思路一：暴力解法

1. 初始化一个变量 result 来存储最短子序列的长度，初始值设为最大整数。
2. 通过两层循环，外层循环遍历子序列的起点，内层循环遍历子序列的终点。
3. 计算从起点到终点的子序列的和 sum。
4. 一旦 sum 大于或等于给定的目标值 target，记录子序列的长度，并更新 result 为更小的长度。
5. 如果 result 保持初始值，说明没有找到符合条件的子序列，返回 0。否则，返回 result。

• 时间复杂度是 O(n^2)，注意后面力扣更新了数据，暴力解法已经超时了
• 外层循环：外层循环遍历数组 nums 的每个元素，作为子序列的起点。如果数组的长度是 n，那么外层循环的时间复杂度是 O(n)。
• 内层循环：对于外层循环中的每一个起点，内层循环遍历从该点开始的所有可能的子序列终点。在最坏的情况下，例如当所有元素之和都小于 target 时，内层循环也会执行 n 次。

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int result = Integer.MAX_VALUE; // 最终的结果
        int sum; // 子序列的数值之和
        int subLength; // 子序列的长度
        for (int i = 0; i < nums.length; i++) { // 设置子序列起点为i
            sum = 0;
            for (int j = i; j < nums.length; j++) { // 设置子序列终止位置为j
                sum += nums[j];
                if (sum >= target) { // 一旦发现子序列和超过了s，更新result
                    subLength = j - i + 1; // 取子序列的长度
                    result = Math.min(result, subLength);
                    break; // 因为我们是找符合条件最短的子序列，所以一旦符合条件就break
                }
            }
        }
        // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
        return result == Integer.MAX_VALUE ? 0 : result;
    }
}

思路二：滑动窗口法

1. 初始化一个变量 result 来存储最短子序列的长度，初始值设为最大整数。
2. 设置两个指针 i 和 j 来表示滑动窗口的起始和终止位置。
3. 遍历数组，扩展窗口的终止位置 j，并累加窗口内的元素和 sum。
4. 当 sum 大于或等于目标值 target 时，计算当前窗口的长度，并更新 result。
5. 缩小窗口的起始位置 i，并从 sum 中减去该位置的元素值。
6. 继续遍历直到数组结束。
7. 如果 result 保持初始值，说明没有找到符合条件的子序列，返回 0。否则，返回 result。

**时间复杂度：**由于数组遍历和窗口调整这两个部分都是线性的,并且它们是并行的（而非嵌套）,所以总时间复杂度 O(n)

• 遍历数组：算法中有一个主循环，它遍历整个数组。每个元素被访问一次，所以这部分的时间复杂度是 O(n)，其中 n 是数组 nums 的长度。
• 窗口调整：在遍历过程中，我们使用两个指针 i 和 j 来定义窗口的边界。这两个指针各自只向前移动，j 指针在主循环中每次向前移动一步，而 i 指针在内部的 while 循环中也总共向前移动 n 次。因此，窗口调整的总操作次数也是线性的，即 O(n)。

• subLength = j - i + 1：计算当前窗口的长度。由于数组索引是从0开始，所以长度是 j - i + 1 而不是 j - i。
• result = Math.min(result, subLength)：更新 result，它保存目前为止找到的满足条件的最短子数组的长度。
• sum -= nums[i++]：这是滑动窗口的关键操作。我们从 sum 中减去窗口起始位置的元素值，然后将起始位置 i 向右移动一位。这个操作相当于缩小了窗口的大小。

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int result = Integer.MAX_VALUE;
        int sum = 0; // 滑动窗口数值之和
        int i = 0; // 滑动窗口起始位置
        int subLength; // 滑动窗口的长度
        for (int j = 0; j < nums.length; j++) {
            sum += nums[j];
            while (sum >= target) {
                subLength = j - i + 1; // 取子序列的长度
                result = Math.min(result, subLength);
                sum -= nums[i++]; // 缩小窗口并更新窗口数值之和
            }
        }
        return result == Integer.MAX_VALUE ? 0 : result;
    }
}

框架解题代码如下

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        // 初始化结果为最大值，便于之后寻找最小值
        int result = Integer.MAX_VALUE;
        // 初始化左右指针
        int left = 0;
        int right = 0;
        // 初始化子数组长度
        int subLength = 0;
        // 初始化窗口内元素和
        int sum = 0;

        // 外层循环控制右指针，遍历数组
        while(right < nums.length) {
            // 将当前右指针指向的元素加入窗口内元素和
            sum += nums[right];
            // 移动右指针
            right++;

            // 内层循环控制左指针，缩小窗口
            // 当窗口内元素和大于等于目标值时尝试缩小窗口以找到更小的满足条件的子数组
            while(sum >= target && left < right) {
                // 计算当前窗口的长度
                subLength = right - left;
                // 更新结果为当前窗口长度和之前结果的较小值
                result = Math.min(result, subLength);
                // 从窗口内元素和中移除左指针指向的元素
                sum -= nums[left];
                // 移动左指针
                left++;
            }
        }

        // 如果结果未被更新过（即没有找到满足条件的子数组），返回0；否则返回结果。
        return result == Integer.MAX_VALUE ? 0 : result;
    }
}

12. 水果成篮

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。

你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：

• 你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
• 你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
• 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。

给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。

示例 1：

输入：fruits = [1,2,1]

输出：3

解释：可以采摘全部 3 棵树。

示例 2：

输入：fruits = [0,1,2,2]

输出：3

解释：可以采摘 [1,2,2] 这三棵树。

如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。

示例 3：

输入：fruits = [1,2,3,2,2]

输出：4

解释：可以采摘 [2,3,2,2] 这四棵树。

如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。

示例 4：

输入：fruits = [3,3,3,1,2,1,1,2,3,3,4]

输出：5

解释：可以采摘 [1,2,1,1,2] 这五棵树。

提示：

• 1 <= fruits.length <= 105
• 0 <= fruits[i] < fruits.length

解题思路如下：力扣链接 (opens new window)

这个问题本质上是要找到最长的子数组，该子数组恰好包含不超过两种不同的水果。这可以看作是一个典型的滑动窗口问题。我们可以用一个滑动窗口来遍历数组，同时用一个数据结构（如哈希表）来记录窗口内每种水果的数量，以确保窗口内最多只有两种水果。当窗口内的水果种类超过两种时，我们需要缩小窗口直到窗口内再次只包含两种水果为止。

1. 初始化：使用一个哈希表来记录每种水果在当前窗口内的数量，初始化左右指针表示窗口的边界，都设为0。还需要一个变量来记录最大数量的水果。
2. 扩展窗口：向右移动右指针，每移动一次，就将对应的水果种类数量加一。同时，检查当前窗口内的水果种类数。
3. 窗口内条件判断和调整：如果窗口内的水果种类超过两种，向右移动左指针，直到窗口内只包含两种水果。每次移动左指针时，相应的水果数量减一。
4. 更新结果：在每次窗口调整后，更新可以收集的最大水果数量。
5. 结束循环：重复步骤2-4直到右指针到达数组末尾。
6. 返回结果：返回记录的最大水果数量。

• 时间复杂度是O(n)，因为每个元素最多被访问两次（一次被右指针访问，一次被左指针访问）

• 空间复杂度是O(1)，因为哈希表存储的是水果种类和数量，水果种类的最大数量是固定的（最多为2种）

解题代码如下

import java.util.HashMap;

class Solution {
    public int totalFruit(int[] fruits) {
        // 用哈希表记录当前窗口内每种水果的数量
        // 键是水果种类，值是该种水果的数量
        HashMap<Integer, Integer> count = new HashMap<>();
        int res = 0; // 用于记录可以收集的最大水果数量
        int left = 0; // 初始化左指针，表示当前考虑的窗口的起始位置

        // 开始遍历数组，移动右指针，表示当前考虑的窗口的结束位置
        for (int right = 0; right < fruits.length; right++) {
            // 将当前右指针指向的水果加入到窗口内
            // 如果这种水果是新种类，就添加到哈希表中
            // 否则，增加这种水果的数量
            count.put(fruits[right], count.getOrDefault(fruits[right], 0) + 1);
            
            // 如果窗口内水果种类超过两种，需要移动左指针缩小窗口
            // 直到窗口内只包含两种水果
            while (count.size() > 2) {
                // 从窗口中移除一种水果
                count.put(fruits[left], count.get(fruits[left]) - 1);
                // 如果某种水果数量减为0，表示完全移除，需要从哈希表中删除记录
                if (count.get(fruits[left]) == 0) {
                    count.remove(fruits[left]);
                }
                left++; // 向右移动左指针
            }
            
            // 更新最大水果数量，当前窗口的大小就是这个窗口内的水果数量
            res = Math.max(res, right - left + 1);
        }
        
        // 遍历结束后，返回记录的最大水果数量
        return res;
    }
}

框架解题代码如下

class Solution {
    public int totalFruit(int[] fruits) {
        // 使用HashMap来记录窗口中各种水果的数量
        HashMap<Integer,Integer> map  = new HashMap<>();
        // 初始化结果变量res，用于记录最长的子数组长度
        int res = 0;
        // 初始化左右指针
        int left = 0;
        int right = 0;
        // 遍历fruits数组
        while(right < fruits.length) {
            // 将当前右指针所指的水果类型加入到map中，并更新计数
            map.put(fruits[right],map.getOrDefault(fruits[right],0) + 1);
            // 扩大窗口，右移右指针
            right++;
            // 当窗口中包含超过两种水果时，开始收缩窗口
            while(left < right && map.size() > 2) {
                // 将左指针所指的水果从窗口中移除一个，并更新计数
                map.put(fruits[left],map.get(fruits[left])-1);
                // 如果某种水果数量减到0，将其从map中移除
                if(map.get(fruits[left]) == 0) {
                    map.remove(fruits[left]);
                }
                // 缩小窗口，右移左指针
                left++;
            }
            // 更新结果res为当前窗口的长度和历史最长窗口长度的最大值
            res = Math.max(res,right-left);
        }
        // 返回结果
        return res;
    }
}

13. 最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

• 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
• 如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"

输出："BANC"

解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2：

输入：s = "a", t = "a"

输出："a"

解释：整个字符串 s 是最小覆盖子串。

示例 3:

输入: s = "a", t = "aa"

输出: ""

解释: t 中两个字符 'a' 均应包含在 s 的子串中，因此没有符合条件的子字符串，返回空字符串。

提示：

• m == s.length
• n == t.length
• 1 <= m, n <= 105
• s 和 t 由英文字母组成

解题思路如下：力扣链接 (opens new window)

• 初始化两个哈希表：
  • tCharCount: 记录字符串t中的字符及其出现次数。这是我们的需求表，记录了我们期望在s的子串中每个字符至少出现的次数。
  • window: 记录当前考察窗口中的字符及其出现次数。这是我们的窗口表，记录了当前窗口中每个字符的实际出现次数。
• 遍历字符串s（扩大窗口）： - 使用右指针right遍历字符串s。每次迭代中，我们将right指向的新字符包含进窗口，并更新window哈希表中对应字符的计数。 - 如果新增字符在tCharCount中，并且其数量满足需求（即window中字符数量等于tCharCount中的数量），我们将valid计数器增加1。这意味着现在窗口中有更多字符满足t的要求。
• 收缩窗口（以找到可能的最小子串）：
  • 当count计数器等于tCharCount中不同字符的数量时（即窗口中已包含t的所有字符），我们检查是否能通过移动左指针left来减小窗口大小。
  • 若当前窗口大小小于之前记录的最小覆盖子串大小（len），我们更新最小覆盖子串的起始位置start和长度len。
  • 移动左指针前将左指针指向的字符从窗口中移除，同时更新window哈希表。如果移除的字符是t中的字符，并且移除后数量不再满足tCharCount的要求，则减少count计数。

• 时间复杂度分析：左指针和右指针各自只负责一次遍历，所以总体时间复杂度是线性的，即O(n)

框架解题解题代码如下

class Solution {
    public String minWindow(String s, String t) {
        // tCharCount 用于记录 t 中的字符及其出现的次数
        HashMap<Character, Integer> tCharCount = new HashMap<>();
        // window 用于记录当前窗口中关于需求表t中出现的字符情况，其他字符不关心
        HashMap<Character, Integer> window = new HashMap<>();
        
        // 初始化 tCharCount
        for (char c : t.toCharArray()) {
            tCharCount.put(c, tCharCount.getOrDefault(c, 0) + 1);
        }
        
        int left = 0, right = 0; // 初始化左右指针
        int count= 0; // 用于判断窗口是否满足条件
        // 初始化记录最小覆盖子串的起始索引及长度
        int start = 0, len = Integer.MAX_VALUE;

        while (right < s.length()) {
            char c = s.charAt(right); // c 是将要移入窗口的字符
            right++; // 增大窗口
            // 进行窗口内数据的一系列更新
            if (tCharCount.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                // 如果窗口表中c对应的个数和需求表c对应的个数一致，那么count++
                if (window.get(c).equals(tCharCount.get(c))) {
                    count++;
                }
            }

            // 判断左侧窗口是否要收缩（如果哈希表中符合的种类与需求表中一致，那么可以缩小窗口）
            while (count== tCharCount.size()) {
                // 更新最小覆盖子串的起始索引位置和数组剩余位置的最大长度
                if (right - left < len) {
                    start = left;
                    len = right - left;
                }
                char d = s.charAt(left); // d 是将要移出窗口的字符
                left++; // 缩小窗口
                // 进行窗口内数据的一系列更新
                if (tCharCount.containsKey(d)) {
                    //  如果窗口表中d对应的个数和需求表d对应的个数一致
                    // 那么此时移除d意味着窗口里面包含的字符不符合需求表里的要求，那么count--
                    if (window.get(d).equals(tCharCount.get(d))) {
                        count--;
                    }
                    // 移除d缩小窗口表大小
                    window.put(d, window.get(d) - 1);
                }
            }
        }
        // 返回最小覆盖子串
        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }
}

14. 字符串的排列

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false

换句话说，s1 的排列之一是 s2 的 子串 。

示例 1：

输入：s1 = "ab" s2 = "eidbaooo"

输出：true

解释：s2 包含 s1 的排列之一 ("ba").

示例 2：

输入：s1= "ab" s2 = "eidboaoo"

输出：false

提示：

• 1 <= s1.length, s2.length <= 104
• s1 和 s2 仅包含小写字母

解题思路如下：力扣链接 (opens new window)

思路一：暴力解法

暴力解法的核心思想是检查s2中的每个长度为s1长度的子串，看是否有任何一个子串是s1的排列。

1. 统计s1中每个字符的出现次数：遍历s1，统计每个字符出现的次数并存储在一个哈希表s1Count中。
2. 枚举s2中的所有长度为s1长度的子串：从s2的第一个字符开始，检查每个长度为s1.length()的子串。
3. 检查子串是否为s1的排列：
   • 对于s2的每个这样的子串，统计子串中每个字符的出现次数，并存储在另一个哈希表s2SubCount中。
   • 比较这两个哈希表。如果它们相等，意味着当前子串是s1的排列之一，返回true。
4. 返回结果：如果所有子串都不是s1的排列，最终返回false。

• 时间复杂度是O(n*m)，其中n和m分别是s1和s2的长度

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        // s1Count 用于记录 s1 中的字符及其出现的次数
        HashMap<Character, Integer> s1Count = new HashMap<>();
        for (char c : s1.toCharArray()) {
            s1Count.put(c, s1Count.getOrDefault(c, 0) + 1);
        }

        // 枚举 s2 中所有长度为 s1.length() 的子串
        for (int i = 0; i <= s2.length() - s1.length(); i++) {
            // s2SubCount 用于记录当前子串中的字符及其出现的次数
            HashMap<Character, Integer> s2SubCount = new HashMap<>();
            for (int j = 0; j < s1.length(); j++) {
                char c = s2.charAt(i + j);
                s2SubCount.put(c, s2SubCount.getOrDefault(c, 0) + 1);
            }
            // 如果当前子串的字符统计与 s1 相同，则返回 true
            if (s1Count.equals(s2SubCount)) {
                return true;
            }
        }
        // 如果没有找到符合条件的子串，则返回 false
        return false;
    }
}

思路二：滑动窗口（模板解）

1. 初始化哈希表：
   • s1Count：记录字符串s1中每个字符的出现次数。
   • window：记录当前窗口中每个字符的出现次数。
2. 滑动窗口遍历s2：
   • 使用两个指针left和right表示当前考虑的窗口的左右边界。窗口中是s2的一部分子串。
   • 使用count来记录当前窗口中字符数量与s1Count相匹配的字符种类数量。
3. 扩展窗口：
   • 移动右指针right，扩展窗口，直到窗口大小等于或超过s1的长度。
   • 更新窗口中字符的出现次数，如果字符在s1Count中，相应更新count。
4. 收缩窗口：
   • 当窗口大小超过s1的长度时，尝试通过移动左指针left来收缩窗口，同时更新窗口内的数据。
5. 检查当前窗口是否满足条件：
   • 如果count等于s1Count中记录的不同字符的数量，返回true。
6. 返回结果：
   • 如果在整个s2中都没有找到满足条件的子串，最终返回false。

• 时间复杂度为O(n)，其中m是s1的长度，n是s2的长度

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        HashMap<Character,Integer> s1Count = new HashMap<>();
        HashMap<Character,Integer> window = new HashMap<>();

        // 统计s1中每个字符的出现次数
        for(int i = 0; i < s1.length(); i++) {
            char c = s1.charAt(i);
            s1Count.put(c, s1Count.getOrDefault(c, 0) + 1);
        }

        int left = 0;
        int right = 0;
        int count = 0; // 记录窗口中满足s1Count条件的字符种类数

        // 开始遍历s2
        while(right < s2.length()) {
            char c = s2.charAt(right);
            right++; // 扩大窗口
            // 如果c是s1中的字符，则更新窗口数据
            if(s1Count.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                // 如果窗口中c的数量达到了s1中c的数量，更新count
                if(window.get(c).equals(s1Count.get(c))) {
                    count++;
                }
            }

            // 当窗口大小等于或超过s1长度时，开始尝试收缩窗口
            while(right - left >= s1.length()) {
                // 收缩窗口之前判断该窗口是不是我们要找的字符串
                // 如果count和s1Count中字符种类数相等，返回true
                if(count == s1Count.size()) {
                    return true;
                }
                char d = s2.charAt(left);
                left++; // 收缩窗口
                // 更新窗口内的数据
                if(s1Count.containsKey(d)) {
                    if(window.get(d).equals(s1Count.get(d))) {
                        count--; // 如果d字符数量减少后不再满足条件，更新count
                    }
                    window.put(d, window.get(d) - 1);
                }
            }
        }
        return false; // 遍历完s2后，没有找到符合条件的子串
    }
}

15. 找到字符串中所有的字母异位词

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

示例 1:

输入: s = "cbaebabacd", p = "abc"

输出: [0,6]

解释:

起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。

起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

示例 2:

输入: s = "abab", p = "ab"

输出: [0,1,2]

解释:

起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。

起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。

起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

提示:

• 1 <= s.length, p.length <= 3 * 104
• s 和 p 仅包含小写字母

解题思路如下：力扣链接 (opens new window)

这个题目的核心是在一个字符串 s 中找到所有的子串，这些子串是另一个字符串 p 的字母异位词。字母异位词是指由相同的字母以不同的顺序排列形成的单词或短语。换句话说，这个问题是要求你在字符串 s 中找到所有可能的、由字符串 p 中的字母重新排列组成的子串，并返回这些子串在 s 中的起始索引。

具体来说，例子中的示例可以解释如下

• 输入的字符串 s 是 "cbaebabacd"，字符串 p 是 "abc"。
• 字符串 "abc" 的异位词包括 "abc", "bac", "cab", "acb", "bca", "cba" 等，即所有由这三个字母组成的不同排列。
• 在字符串 s 中，"cba"（位于索引 0）和 "bac"（位于索引 6）是字符串 "abc" 的异位词。
• 因此输出是这两个子串的起始索引：[0, 6]。

这是一个典型的滑动窗口类型的问题，可以通过维护一个固定长度的窗口在 s 上滑动，并在每个位置检查窗口内的字符是否与 p 的字符相匹配（无论顺序如何）来解决。

1. 初始化两个哈希表：tCount 和 window。tCount 记录字符串 t 中每个字符的出现次数，window 记录当前窗口中各字符的出现次数。
2. 初始化两个指针：left 和 right 分别表示窗口的左右边界。
3. 初始化变量 count：用于记录窗口中满足 tCount 条件的字符的数量。
4. 开始滑动窗口：移动右指针 right，扩大窗口，并更新 window 中的数据。如果右指针指向的字符在 tCount 中，更新 window 中该字符的计数，并且如果 window 中该字符的计数与 tCount 相等，count 加一。
5. 检查并收缩窗口：当窗口大小等于 t 长度时，如果 count 与 tCount 大小相同，说明窗口内的字符串是 t 的一个异位词，记录窗口左指针 left 的位置。然后，移动左指针，缩小窗口，并更新 window 和 count。
6. 记录结果：如果窗口内的字符串是 t 的一个异位词，则将当前左指针的位置添加到结果列表 res 中。
7. 返回结果：返回列表 res，包含所有异位词的起始索引。

• 时间复杂度是 O(N)，其中 N 是字符串 s 的长度。这是因为我们需要遍历整个字符串 s，而在每个窗口位置上的操作是常数时间的

哈希表+滑动窗口解题

class Solution {
    public List<Integer> findAnagrams(String s, String t) {
        Map<Character, Integer> tCount= new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();
        // 初始化 tCount表
        for (char c : t.toCharArray()) {
		tCount.put(c, tCount.getOrDefault(c, 0) + 1);
	}

        int left = 0, right = 0;
        int count = 0; // 满足 tCount条件的字符数
        List<Integer> res = new ArrayList<>(); // 存放结果
        while (right < s.length()) {
            char c = s.charAt(right);
            right++;
            // 更新窗口内数据
            if (tCount.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                if (window.get(c).equals(tCount.get(c))) count++;
            }
            // 检查窗口是否需要收缩
            while (right - left >= t.length()) {
                if (count == tCount.size()) res.add(left); // 记录结果
                char d = s.charAt(left);
                left++;
                // 更新窗口内数据
                if (tCount.containsKey(d)) {
                    if (window.get(d).equals(tCount.get(d))) count--;
                    window.put(d, window.get(d) - 1);
                }
            }
        }
        return res; // 返回结果
    }
}

16. 无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = "abcabcbb"

输出: 3

解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: s = "bbbbb"

输出: 1

解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew"

输出: 3

解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。

请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

提示：

• 0 <= s.length <= 5 * 104
• s 由英文字母、数字、符号和空格组成

解题思路如下：力扣链接 (opens new window)

使用滑动窗口算法来找出字符串s中不含有重复字符的最长子串的长度

1. 初始化窗口哈希表：
   • window：记录当前窗口中每个字符的出现次数。
2. 初始化其它变量：
   • len：用来记录无重复字符的最长子串的长度。
   • 使用两个指针left和right表示当前考虑的窗口的左右边界。窗口中是s的一部分子串。
3. 遍历s字符串：
   • 使用右指针right表示当前考虑的窗口的右边界，逐步扩展窗口。
   • 更新窗口中字符的出现次数。
   • 检查窗口内是否有重复字符。
4. 收缩窗口：
   • 如果窗口内有重复字符，则移动左指针left以移除字符，直到窗口中不再有重复字符。
5. 更新最长子串的长度：
   • 在每次窗口更新后，如果当前窗口内无重复字符，更新最长子串长度。
6. 返回结果：
   • 最终返回最长无重复字符子串的长度。

• 时间复杂度为O(n)，尽管有两个while循环嵌套，但每个字符最多被加入和移除各一次，所以它们的复杂度仍然是线性的。

框架解题代码如下

class Solution {
    public int lengthOfLongestSubstring(String s) {
        HashMap<Character,Integer> window = new HashMap<>(); // 当前窗口中的字符及其出现次数
        int left = 0, right = 0, len = 0; // 初始化左右指针和最长子串长度

        // 开始遍历s
        while(right < s.length()) {
            char c = s.charAt(right); // 即将加入窗口的字符
            right++; // 扩大窗口
            // 更新窗口内的数据
            window.put(c, window.getOrDefault(c,0)+1);

            // 如果窗口中出现重复字符，开始移动左指针收缩窗口
            while(window.get(c) > 1) {
                char d = s.charAt(left); // 即将移出窗口的字符
                left++; // 收缩窗口
                window.put(d, window.get(d)-1); // 更新窗口内的数据
            }
            // 更新最长无重复字符子串的长度
            len = Math.max(len, right-left);
        }
        return len; // 返回最长无重复字符子串的长度
    }
}

17. 螺旋矩阵II

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix

示例 1：

输入：n = 3

输出：[[1,2,3],[8,9,4],[7,6,5]]

示例 2：

输入：n = 1

输出：[[1]]

提示：

• 1 <= n <= 20

解题思路如下：力扣链接 (opens new window)

1. 初始化二维矩阵：创建一个 n x n 的矩阵，准备在其中填充数字。
2. 确定循环圈数：计算螺旋的圈数。如果 n 是奇数，中间会剩下一个单独的格子。
3. 螺旋填充数字：从外圈开始，逐圈向内填充数字。每一圈包括四个步骤：上、右、下、左。
4. 调整起始点和边界：每完成一圈，起始点向内移动一格，同时缩减遍历的边界。
5. 处理中心点：如果 n 是奇数，最后填充中心格子。

• 时间复杂度是 O(n^2)。这意味着操作次数与矩阵大小的平方成正比
• 遍历和填充：算法的核心是通过一系列的循环来遍历矩阵并填充它。每个元素在算法中仅被访问和填充一次。
• 矩阵大小：矩阵的总大小是 n x n，所以它包含 n^2 个元素。
• 总操作次数：因为每个元素只处理一次，并且矩阵中有 n^2 个元素，所以总的操作次数也就是 n^2 次。

为什么需要 n - offset：

在每一圈螺旋中，右边界和下边界都在逐渐向内缩小。这是因为每完成一圈，整个螺旋的范围就减少了。offset 变量就是用来控制这个缩减的，它确保了每一圈都比上一圈小一圈。

解题代码如下

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] res = new int[n][n]; // 创建n x n的矩阵
        int startx = 0, starty = 0; // 起始位置坐标
        int loop = n / 2; // 计算螺旋的圈数
        int mid = n / 2; // 如果n是奇数，中心点的坐标
        int count = 1; // 计数器，用于填充数字
        int offset = 1; // 每一圈边界的缩减量

        while (loop-- > 0) { // 按圈数进行循环
            int i = startx, j = starty; // 初始化i和j为起始坐标

            // 填充上边（从左上角到右上角）
	    // i = startx，i（行）不变，j（列）向右移动
            for (j = starty; j < n - offset; j++) {
                res[i][j] = count++;
            }
            // 填充右边（从右上角到右下角）
	    // j = starty，j（列）不变，i（行）向下移动，
            for (i = startx; i < n - offset; i++) {
                res[i][j] = count++;
            }
            // 填充下边（从右下角到左下角）
            // i = startx，i（行）不变，j（列）向左移动，starty是本圈的左边界
            for (; j > starty; j--) {
                res[i][j] = count++;
            }
            // 填充左边（从左下角到左上角）
            // j = starty，j（列）不变，i（行）向上移动，startx是本圈的上边界
            for (; i > startx; i--) {
                res[i][j] = count++;
            }

            // 更新起始位置和边界
            startx++;
            starty++;
            offset += 1;
        }

        // 如果n是奇数，填充中心点
        if (n % 2 != 0) {
            res[mid][mid] = count;
        }
        return res;
    }
}