← 返回首页

第八章-数组算法

第八章：数组算法 (Array Algorithms)

学习内容

数组是最基础的数据结构，相关的算法题也非常丰富，双指针、二分搜索和滑动窗口是解决数组问题的核心技巧。

双指针技巧

双指针是数组问题中最常用的技巧之一，主要有以下几种类型：

#### 快慢指针


#### 左右指针


#### 滑动窗口


二分搜索

二分搜索是处理有序数组的经典算法，时间复杂度为 O(log n)。

#### 基本模板
1. 标准二分搜索：在有序数组中查找目标值
2. 左侧边界二分搜索：寻找目标值的左边界
3. 右侧边界二分搜索：寻找目标值的右边界

#### 应用场景



前缀和与差分数组

#### 前缀和


#### 差分数组


重点和难点

重点


1. 掌握双指针技巧在数组中的应用
2. 理解并熟练使用二分搜索的三种模板
3. 熟悉前缀和与差分数组的应用场景

难点


1. 滑动窗口的边界处理
2. 二分搜索的细节控制
3. 复杂问题中多种技巧的结合使用

练习题

双指针经典题


1. 移动零 (Move Zeroes)
- 题目：给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
- 解题思路：使用快慢指针，慢指针指向下一个非零元素应该放置的位置。
- 注意点：必须在不复制数组的情况下原地对数组进行操作。

2. 盛最多水的容器 (Container With Most Water)
- 题目：给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
- 解题思路：使用左右双指针，每次移动较短的那条边。
- 注意点：理解为什么移动较短边是正确的策略。

二分搜索题


1. 搜索旋转排序数组 (Search in Rotated Sorted Array)
- 题目：整数数组 nums 按升序排列，数组中的值互不相同。在传递给函数之前，nums 在预先未知的某个下标 k 上进行了旋转。给你旋转后的数组 nums 和一个整数 target，如果 nums 中存在这个目标值 target，则返回它的下标，否则返回 -1。
- 解题思路：先找到旋转点，然后在有序部分进行二分搜索；或者直接使用改进的二分搜索。
- 注意点：需要仔细处理各种边界情况。

2. 在排序数组中查找元素的第一个和最后一个位置 (Find First and Last Position of Element in Sorted Array)
- 题目：给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
- 解题思路：使用左侧边界和右侧边界二分搜索模板。
- 注意点：注意处理目标值不存在的情况。

滑动窗口题


1. 最小覆盖子串 (Minimum Window Substring)
- 题目：给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。
- 解题思路：使用滑动窗口，右指针扩展窗口，左指针收缩窗口，维护窗口内的字符统计。
- 注意点：注意处理字符频次的统计和窗口的扩张收缩条件。

2. 长度最小的子数组 (Minimum Size Subarray Sum)
- 题目：给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其和 ≥ target 的长度最小的连续子数组，并返回其长度。
- 解题思路：使用滑动窗口，右指针扩展窗口，左指针收缩窗口。
- 注意点：注意处理没有满足条件子数组的情况。

解题思路总结

双指针技巧的使用场景


1. 快慢指针：用于处理数组元素的移动、删除等问题
2. 左右指针：用于处理有序数组的查找、计算问题
3. 滑动窗口：用于处理连续子数组、子串问题

二分搜索的三种模板


1. 标准二分：查找确切值
2. 左侧边界：查找第一个满足条件的位置
3. 右侧边界：查找最后一个满足条件的位置

前缀和与差分数组的应用


1. 前缀和：快速计算区间和，避免重复计算
2. 差分数组：频繁对区间进行增减操作时使用

学习时间

建议学习时间：3-4天