【算法刷题】数组题型及方法归纳_c++ 数组常用题型

数组特点

（1）下标从0开始
（2）内存空间的地址连续

因为上述两个特点，所以在对数组进行操作时，第一个是注意操作下标，第二个增、删元素时需要移动元素（注意删除元素其实不是真正的删除，而是用其余的值去覆盖）。

1、左右双指针：查找

二分查找模板
C++

int l = 0, r = n - 1;
while(l <= r){
	int mid = l + (r - l) / 2;
	if(nums[mid] == target) {
		// 找一个数，则 return mid;
		// 找左边界，则 mid = r - 1;
		// 找右边界，则 mid = l + 1;
	} else if(target < nums[mid]) {
		r = mid - 1;	
	} else if(nums[mid] < target) {
		l = mid + 1;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

Python

l, r = 0, len(nums) - 1
while l <= r :
	mid = (l + r) // 2
	if nums[mid] == target :
		// 找一个数，则 return mid
		// 找左边界，则 mid = r - 1
		// 找右边界，则 mid = l + 1
	elif target < nums[mid] :
		r = mid - 1
	elif target > nums[mid] :
		l = mid + 1
1
2
3
4
5
6
7
8
9
10
11

（1）方法：双指针法，数组两端设置左指针和右指针。
（2）注意：边界问题取值。
[,]：左闭右闭，左右两端指针均可以取到对应位置，则为 <=
left = mid + 1 、rigth = mid - 1 、mid = (right + left) / 2
[,)：左闭右开，左可以取到右边取不到，则为<
left = mid + 1、right = mid、mid = (right + left) / 2
(,]：左开右闭，左取不到右边能取到，则为<
left = mid、right = mid - 1、mid = (right + left + 1) / 2

题目：

1. 二分查找（C++、Python3）

2. 39、【查找】二分查找：数的范围和查找某个数（C/C++版）

3. 35. 搜索插入位置
   注意返回值

4. √ 34. 在排序数组中查找元素的第一个和最后一个位置（C++/Python版本）
   分左右边界讨论，寻找左边界时，向左侧区间压缩；寻找右边界时，向右侧区间压缩。

5. AcWing 790. 数的三次方根：浮点数二分（C++/Python版本）
   浮点数二分类型题目

2、左右双指针：非查找

题目：

1. 左右双指针按某种规则依次移动填充
   √ 有序数组的平方+双指针（C++/Python版本）

   （1）特点：一组负数中的最小值平方后会成为最大值。根据这一性质，可知道最大值可能在题中所规定的数组的最左端或最右端。次最大值也与之相同，以此类推，可找到一组有序数。
   （2）方法：双指针法，左右两端设置指针。按照从大到小存储到数组当中。

2. n个数之和且需去重：
   （1）采用排序+双指针的方法，重点是剪枝条件和去重条件。
   73、【数组】leetcode——15. 三数之和（C++/Python版本）

   （2）相比于三数之和，多一层for循环。
   74、【数组】leetcode——18. 四数之和（C++版本）

   （3）数组中已有序，直接用双指针即可，对于非有序的数组，先排序，再双指针。
   AcWing 800. 数组元素的目标和（C++/Python版本）

3. 左右指针实现旋转
   344. 反转字符串
   库函数reverse():是左闭右开，本题通过左右指针，实现了一个左闭右闭的反转函数。

4. 区间合并
   141、【贪心算法】leetcode ——56. 合并区间（区间重叠解法+双指针解法）（C++版本）
   左边界和右边界指针分别指向第一个数中左右边界值，右边界指针与后一个数对比，有重叠则合并，没有重叠则直接添加当前数，然后遍历下一个。

5. 由回文串中心点向两侧延伸指针
   182、【动态规划/数组】leetcode ——647. 回文子串：动态规划+双指针（C++版本）：分别对奇数长度中心点i与偶数长度中心点i和i+1进行判定。

3、快慢双指针法

双指针法，使用快慢指针。快指针用于遍历，慢指针存储。

题目：

1. 对于需移除数组中某一指定元素时，可用本题思路。
   √ 移除链表元素
   用快指针遍历，慢指针进行存储，将符合条件的数值，用慢指针依次覆盖原数组内容。

2. 快慢指针填充元素
   77、【字符串】leetcode ——151. 反转字符串中的单词（C++版本）
   （1）预处理：对于空格的处理，采用和 203. 移除链表元素 同样的 快慢双指针 思路，按照首尾无空格，每个单词间有一个空格进行填充。
   （2）完成预处理后，先对整体逆置，再对每个单词进行逆置。

3. pre与cur指针对比+快慢指针对比填充元素
   84、【栈与队列】leetcode ——225. 用队列实现栈：栈+双指针解法（C++版本）
   对 203. 移除链表元素 思路进行的拓展，在原字符串中多设置一个指针，分别作为pre和cur。每次先pre与cur对比，然后再让快指针指向的源字符串元素和慢指针指向的新字符串元素对比。符合条件，则填充。

4. 两独立指针从后往前填充元素
   76、【字符串】剑指 Offer ——05. 替换空格（C++版本）
   设置两个独立双指针，原字符串末尾位置和新字符串末尾位置各设置一个指针，从后往前填充或替换。

5. 设置pre和cur对比大小关系
   101、【树与二叉树】leetcode ——98. 验证二叉搜索树：递归法[先序+中序+后序]+迭代法（C++版本）
   pre指针记录上一个结点，cur指向当前结点，当上一个结点的值小于当前结点的值，说明为递增关系。
   同类题型：
   105、【树与二叉树】leetcode ——530. 二叉搜索树的最小绝对差：中序遍历递归法+迭代法（C++版本）
   106、【树与二叉树】leetcode ——501. 二叉搜索树中的众数：双指针法+哈希表法（C++版本）

6. 一个指针为整体遍历指针，一个指针为局部目标遍历指针
   178、【数组/动态规划】leetcode ——392. 判断子序列：双指针+动态规划（C++版本）

4、滑动窗口双指针

滑动窗口模板

for(int i = 0, j = 0; j < n; j++){
	// Operation
	while(i <= j && check(i, j))		// Operation i++;
	// Opeartion	
	// res = min(res, j - i + 1) Or res = max(res, j - i + 1)
}
1
2
3
4
5
6

常用于求满足某一条件的连续元素的最大长度或最小长度。

题目：

1. 求出最小滑动窗口长度
   59、【数组】leetcode——209. 长度最小的子数组-滑动窗口：最小窗口（C++、Python版本）
   （1）特点：有序子序列==连续序列+长度最小
   （2）方法：使用快慢指针实现滑动窗口。
   1）先开窗，设置快指针进行遍历。
   2）当到达条件时，再收缩，慢指针开始向前遍历，找到满足条件的最低限度。
   3）最后判断，是否此时的窗口长度为最小长度。

2. 求出最大滑动窗口长度
   √ 60、【数组】leetcode——904. 水果成篮-滑动窗口：最大窗口（C++版本）
   滑动窗口+Hash表，若在Hash表中查到重复元素，则收缩左区间。

3. 求出最大滑动窗口长度
   63、【数组】AcWing 799. 最长连续不重复子序列（C++版本）
   判定右指针移动时，若有重复元素，则收缩则区间。

4. 单调队列+滑动窗口
   √ 86、【栈与队列】leetcode ——39. 滑动窗口最大值：单调队列+滑动窗口（C++版本）

5. 求出最长连续递增子序列长度（等价于满足某种条件的最大滑动窗口长度）
   174、【动态规划/贪心算法/滑动窗口】leetcode ——674. 最长连续递增序列：一题多解 （C++版本）
   每次移动右指针，满足递增且连续，则继续向下遍历。不满足时，则退出找出最大长度并更新起起始位置。

5. 螺旋矩阵问题：边界收缩 / 起点更新+控制偏移量

题目

1. √ 61、【数组】leetcode——[高频考题]59. 螺旋矩阵 II：N*N型（C++、Python版本）

   方法一：
   （1）方法：边界收缩。记录矩阵的上、下、左、右边界的标号，按顺序每填充完一侧后，就移动一侧边界。

   方法二：
   （1）注意：边界取值，规定全为[,)
   （2）方法：设置起点，每遍历完一圈后更新。设置填充顺序。设置填充长度，通过一个偏移量来控制，都以左闭右开作为填充边界。

2. √ 62、【数组】leetcode——54. 螺旋矩阵：N*M型（C++、Python版本）

   注意N*M型，需先判定边界的相对位置，再遍历。

6、前缀和

前缀和是数组中某一下标中之前的元素元素之和，主要用于快速求出某段区间内元素的和。

计算前缀和模板

s[i] = 0;
for(int i = 0; i < n; i++) {
	s[i + 1] += s[i] + nums[i];
}
1
2
3
4

此时，s中的下标0对应的是0，下标1对应的是nums[0]，下表2对应的是nums[0] + nums[1]，及前缀和数组s中的下标i对应着nums[0 ... i - 1]。如果想要计算区间[i .. j]内的元素之和，则元素之和为s[j + 1] - s[i]。

1. 结合区间dp，由小到大枚举区间长度。
   190、【动态规划】AcWing ——282. 石子合并（C++版本）

2. 结合哈希表，找到前缀和相同的位置，计算最长区间长度
   201、【数组】leetcode ——面试题 17.05. 字母与数字（C++版本）

3. 结合哈希表，找到相同的前缀和，两两配对每次加上出现对应前缀和的次数，计算最长区间长度
   202、【数组】leetcode ——2588. 统计美丽子数组数目（C++版本）