腾讯网微信公众平台/小程序seo推广技巧

数组

二分查找

本节对应代码随想录中：代码随想录-二分查找

原理

二分法（Binary Search）是一种在有序数组中查找特定元素的算法。它的原理是，将数组分成两半，然后判断目标元素在哪一半中，然后再继续将这一半分成两半，直到找到目标元素或者确定目标元素不存在为止。

前提条件：二分法适用于有序数组或有序列表中的查找操作，且元素必须支持比较操作。

一旦有重复元素的时候，二分法返回的下标可能不唯一

算法步骤如下：

1.将数组按照中间元素分成两部分。

2.如果中间元素等于目标元素，直接返回中间元素的下标。

3.如果中间元素大于目标元素，说明目标元素在左半部分，将右边界移动到中间元素的左边。

4.如果中间元素小于目标元素，说明目标元素在右半部分，将左边界移动到中间元素的右边。

5.重复以上步骤，直到找到目标元素或者确定目标元素不存在。

习题

题目1

704. 二分查找
给定一个 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        

提示：

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

思路和代码

这道题目说了元素是有序的，而且无重复元素，那么在查找的时候就可以使用二分法进行查找

写二分法会遇到三种情况

• 初始 right = nums.size()-1 还是 nums.size()
• 是 right = middle-1 还是 right = middle
• 是 while(left <= right) 还是 while(left < right)

如下面这张图，left 等不等于 right，right 的取值也会不一样，可分为两种写法

• 如果初始写 right=nums.size()-1 即7个元素中 L=0，R=6，那么查找区间就是[0,6]，M 为3。
• 此时应该写 right = middle-1 。如上图 M=3时没有匹配成功，那么下次的区间应该是[0,2]，因为 M=3已经判断一次了
• 如上图如果 M=1时仍不是我们要找的元素，假如此时还是大于待查找元素，那么 R=0。此时 left=right=0是有意义的，也就是我们需要最后判定下 L=0时的1是不是待查找元素，因此 while 的条件为 while(left <= right)

这三种情况其实就是要互相对应，第二种类型在代码随想录中有解释

代码如下

class Solution {
public:int search(vector<int>& nums, int target) {int left = 0;int right = nums.size() - 1; // 定义target在左闭右闭的区间里，[left, right]while (left <= right) { // 当left==right，如区间[3, 3]依然有效，所以用 <=int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2if (nums[middle] > target) {right = middle - 1; // middle已经判断过了，下一个右边界应该是middle-1而不是middle} else if (nums[middle] < target) {left = middle + 1; // target 在右区间，所以[middle + 1, right]} else { // nums[middle] == targetreturn middle; // 数组中找到目标值，直接返回下标}}// 未找到目标值return -1;}
};

注意取中间值时没有使用 middle = (left + right) / 2 而是 middle = left + ((right - left) / 2)

这样写能够避免 left + right 可能数值太大导致溢出的问题

例子：在闭区间[3,9]中 right-left=6，说明3到9需要走6步，再除2得3，说明从3到9走3步可以走到中间的位置

题目-2

35.搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 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

代码如下

class Solution {public:int searchInsert(vector<int>& nums, int target) {int n = nums.size();int left = 0, right = n - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] == target) {return mid;} else if (nums[mid] > target) {right = right - 1;} else {left = left + 1;}}return left;}
};

观察上述代码可以发现这题和上题只是在上题 return -1 处改成了 return left

解释： 上题的 return -1 和这里的 return left 都代表着所查找元素没有出现给定数组中的情况

至于目标值被插入的顺序为什么是 left。根据 if 的判断条件，left 左边的值一直保持小于 target，right 右边的值一直保持大于等于 target，而且 left 最终一定等于 right+1

• 左边：[2,4]查找1，left=0，right=1，一轮后 left=0，right=-1
• 中间：[2,4]查找3，left=0，right=1，一轮后 left=1，right=1，二轮后 left=1，right=0
• 右边：[2,4]查找5，left=0，right=1，一轮后 left=1，right=1，二轮后 left=2，right=1

当 left=right=middle 时，若仍未找到，此时要么 right-- 要么 left++，最终一定是 left=right+1

这么一来，循环结束后，left 左边的部分全部小于 target，所以最终答案一定在 left 的位置

参考：搜索插入位置- 力扣（LeetCode）

移除元素

本节对应代码随想录中：代码随想录

习题

题目链接： 27. 移除元素- 力扣（LeetCode）

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

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

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

示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。

示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

你不需要考虑数组中超出新长度后面的元素。

我的想法

非较优答案，仅为个人思路记录

我的想法是 for 循环从头遍历 nums，并用 res 记录最终结果初始为0。如果当前遍历到的值等于 val，则让 res 位置和遍历到的 val 所在位置替换下，这样一轮 for 循环后前 res 位置都是 val。

新的长度用总长度减去 res 即可。而由于题目要求 nums 前 res 个要返回非 val 的数值，因此还要一轮 for 循环将前 res 个元素和后 res 个元素替换。

class Solution {public:int removeElement(vector<int>& nums, int val) {int n = nums.size(), res = 0, temp;for (int i = 0; i < n; i++) {if (nums[i] == val) {// 如果和val相等则和让当前值和前面的值替换temp = nums[i];nums[i] = nums[res];nums[res] = temp;res++;}}// 把和val相等的几个值放到后面for (int i = 0; i < res; i++) {temp = nums[i];nums[i] = nums[n - i - 1];nums[n - i - 1] = temp;}return n - res;}
};

后来看了题解后，想了下发现前 res 个可以直接删除而不用和后面 res 个替换

nums.erase(nums.begin(), nums.begin() + res);

暴力解法

两层 for 循环，第一层循环从头遍历数组，如果遇到和 val 相等的值，则用第二层 for 循环将当前位置之后的元素都像前移动一位。

例如 0 1 2 3 2 5，val=2

• 第一层 for 循环从左到右遍历，遇到 nums[2]=2时，将后面的 3 2 5向前移一位变成0 1 3 2 5
• 接着继续遍历(3 2 5)，遇到第二个2时，将后面的5向前移一位变成0 1 3 5

题目中说了不用考虑超过新长度范围外的元素

代码如下：

需要注意的是向前移动一位后，i 要减1，如上面的例子，nums[2]=2，移动后变成0 1 3 2 5，此时若不减1下一次 i=3，将会跳过3与 val 的比较而是比较第二个2与 val。同时 size 减一方便记录新数组的长度。

// 时间复杂度：O(n^2)
// 空间复杂度：O(1)
class Solution {
public:int removeElement(vector<int>& nums, int val) {int size = nums.size();for (int i = 0; i < size; i++) {if (nums[i] == val) { // 发现需要移除的元素，就将数组集体向前移动一位for (int j = i + 1; j < size; j++) {nums[j - 1] = nums[j];}i--; // 因为下标i以后的数值都向前移动了一位，所以i也向前移动一位size--; // 此时数组的大小-1}}return size;}
};

与我自己想的解法相比，这个解法在找到 val 时将后面的元素向前移动一位，从而保证前面的元素都是题目要求的。

而我的解法是将找到的 val 放到前面，之后再把他们放到后面(直接放到后面会覆盖后面的元素)。

双指针

双指针：通过一个快指针和慢指针在一个for循环下完成两个for循环的工作

快指针从头遍历元素指向当前将要处理的元素，慢指针指向下一个将要赋值的位置。

• 如果快指针指向的元素不等于 val，它一定是输出数组的一个元素，我们就将快指针指向的元素复制到慢指针位置，然后将两个指针同时右移；
• 如果快指针指向的元素等于 val，它不能在输出数组里，此时慢指针不动，快指针右移一位。

这样左边的元素都不等于 val

与前面的两个解法相比，用慢指针替代了前面的第二个 for 循环。关键语句是 nums[slowIndex++] = nums[fastIndex]; 将后面的值直接复制到前面合适的位置。

// 时间复杂度：O(n)
// 空间复杂度：O(1)
class Solution {
public:int removeElement(vector<int>& nums, int val) {int slowIndex = 0;for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) {if (nums[fastIndex] != val) {nums[slowIndex++] = nums[fastIndex];}}return slowIndex;}
};

这里的快指针相当于常写的 for (int i = 0; i < size; i++) 中的 i 一样，遇到和 val 相等的值时，再用一个慢指针将和 val 相等的值移到前面。如果将 fastIndex 改成常写的 i 就会发现其实就是用 nums[slowIndex++] = nums[fastIndex]; 解决了上面两种解法好几行才能解决的问题。

class Solution {
public:int removeElement(vector<int>& nums, int val) {int slowIndex = 0;for (int i = 0; i < nums.size(); i++) {if (nums[i] != val) {nums[slowIndex++] = nums[i];}}return slowIndex;}
};

总结：

• 我的想法遇到和 val 相等的元素先替换到前面再替换到后面
• 暴力解法遇到 val 相等的元素时，将后面的元素都向前移一位
• 双指针遇到 val 相等的元素时，用慢指针将后面的非 val 元素替换到前面的合适位置

有序数组的平方

本节对应代码随想录中：代码随想录，讲解视频：有序数组的平方_哔哩哔哩_bilibili

习题

题目链接：977. 有序数组的平方 - 力扣（LeetCode）

给你一个按非递减顺序排序的整数数组 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]

暴力排序

直接能想到的就是先把每个元素平方，然后再进行排序即可

class Solution {
public:vector<int> sortedSquares(vector<int>& A) {for (int i = 0; i < A.size(); i++) {A[i] *= A[i];}sort(A.begin(), A.end()); // 快速排序return A;}
};

双指针

首先来说一下为什么可以使用双指针

元素本来就是有序的，只不过因为里面有负数，负数平方后就可能大于某些正数的平方，从而顺序会发生变化

但是无论正数还是负数，其绝对值越大，那么它平方后也就会越大，即数组越靠近两边，平方后就会越大

那么我们就可以使用双指针，一个指向最左边，一个指向最右边。比较两边哪个平方后更大，存入新的数组中。然后更新指针，直到两个指针相遇，说明遍历完了所有的元素。

我的解法如下：

class Solution {public:vector<int> sortedSquares(vector<int>& nums) {int n = nums.size(), j = n - 1, k = n - 1;vector<int> copy = nums;for (int i = 0; i < n; i++,k--) {if (i == j) {nums[0] = copy[i] * copy[i];break;}if (copy[i] * copy[i] > copy[j] * copy[j]) {nums[k] = copy[i] * copy[i];} else {nums[k] = copy[j] * copy[j];j--;i--;}   }return nums;}
};

看了别人的解法有几点可以注意下

• vector<int> copy = nums; 也可以写成 vector<int> copy(nums.size(), 0);，区别是前者会复制 nums 的元素，而后者会将所有元素置0
• for 循环中的 i<n 可以 i <= j;，这样就不用再用 if 判断相等时 break 了
• for 循环中的 i++,k-- 可以在 for 循环里面写，其实这样更符合逻辑，因为并不是每次都要 i++,k-- ，只有满足特定情况时才会这样
• 不一定要用 for 循环，用 while(i<=j) 来循环更符合逻辑

双指针思考：上一小节的移除元素中，两个指针都在最左边开始，只不过一个快点，一个慢点，快的用来遍历一遍元素，慢的用来指向满足条件的新的数组的下标；而这一节的双指针，一个在左边，一个在右边，两个指针不断比较，然后都往中间靠拢。上一小节的终止条件是快的指针遍历完一遍就停，而这一节的是当两个指针相遇时(i <= j;)停止

长度最小的子数组

本节对应代码随想录中：代码随想录，讲解视频：拿下滑动窗口！ | LeetCode 209 长度最小的子数组_哔哩哔哩_bilibili

习题

题目链接：209. 长度最小的子数组 - 力扣（LeetCode）

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

暴力解法

直接能想到的就是用两个 for 循环，第一个循环遍历起始位置，第二个 for 循环向后遍历直到找到满足其和 ≥ target 的位置，我的代码如下(非最优，并且会超时，仅用于个人分析记录)：

class Solution {public:int minSubArrayLen(int target, vector<int>& nums) {int res = 999999;for (int i = 0; i < nums.size(); i++) {int sum = 0, count = 999999;for (int j = i; j < nums.size(); j++) {sum += nums[j];if (sum >= target) {count = j - i + 1;break;}}if (count < res) {res = count;}}if(res!=999999){return res;}return 0;}
};

比较代码随想录上的暴力解法，有以下几点可以注意下

• 初始 res 时本意是想初始一个比较大的值，用 res=INT32_MAX 更好
  • INT_MAX 一般和 INT32_MAX 相同，但如果是16位时， INT_MAX 要更小点，所以用 INT32_MAX 更好
• 代码中后面两个 if 判断换成三元运算符更好，即 ` ? :

滑动窗口

C++中的滑动窗口是一种常见的数组/字符串问题的解决方案，它可以将一个问题的时间复杂度从 O(n^2)降低到 O(n)或者 O(nlogn)，通常涉及到从给定的数据序列中找到需要进行操作的子串或子序列等。

滑动窗口的基本思路是：用两个指针表示现在关注的区间，即左端点(left pointer)和右端点(right pointer)，让其构成一个窗口。移动右指针扩大长度，直到包含满足条件的子串（比如大于等于target）。然后，尝试缩小左端点以尽可能的减小满足条件的窗口长度，同时继续移动右指针，查找再次满足条件的子串。重复这个过程直到最右侧，得到最优解。

暴力解法中我们是遍历窗口的初始位置，对于每个初始位置向后遍历剩余元素寻找满足条件的窗口。而滑动窗口是遍历窗口的结束位置，如果当前窗口满足条件，那左边的指针就要向右移动即缩小窗口，其实也算是双指针。

class Solution {public:int minSubArrayLen(int target, vector<int>& nums) {int left = 0, sum = 0,subLength = 0;int ans = INT32_MAX;  // 答案初始化为整数最大值for (int right = 0; right < nums.size(); right++) {sum += nums[right];while (sum >= target) {  // 当sum>=target时，意味着当前窗口的总值大于等于target了subLength = (right - left + 1);  // 取子序列的长度ans = ans < subLength ? ans : subLength;  // 更新anssum -= nums[left]; // 窗口右移那就要减去原来窗口左边的值left++;  // 通过左指针向右移动收缩窗口}}return ans == INT32_MAX ? 0 : ans;  // 如果没找到就返回0}
};

代码中 while (sum >= target) 使用的是 while 而不是 if，因为当缩小窗口的时候是一个循环的过程。

如1 1 1 4中 target=4，那找到满足条件的窗口=4的时候，左指针应该是从初始的1不断向右移动直到新的窗口不大于等于 target 时停止

螺旋矩阵 II

本节对应代码随想录中：代码随想录，讲解视频：一入循环深似海 | LeetCode：59.螺旋矩阵II_哔哩哔哩_bilibili

习题

题目链接：59. 螺旋矩阵 II - 力扣（LeetCode）

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

示例 1：
输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]

我的解法

题目有点像本科时做过的迷宫类题目，数字的增长顺序为右、下、左、上，然后接着按照这个顺序填充。

那么就可以定义一个数组表示每个方向的 x 和 y 应该如何变化，再定义一个 n*n 的数组表示是否访问过当前位置

按照右、下、左、上的顺序去填充矩阵，如果下一个位置在矩阵范围内并且还没有访问过那就填充，否则说明走到头该换方向了，代码如下。

class Solution {public:vector<vector<int>> generateMatrix(int n) {// 4个方向：右下左上int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};vector<vector<int>> nums(n,vector<int>(n));int count = 1;  // 计数int x = 0, y = 0, d = 0;    // x和y的坐标,d代表当前方向// 是否填充过当前位置int isV[n][n];for(int i=0; i<n; i++){for(int j=0; j<n; j++){isV[i][j] = 0;}}// 初始填充[0][0]位置nums[0][0]=count;isV[0][0]=1;while (1) {if (count == n * n) {break;}int newX= x + dir[d][0],newY=y + dir[d][1]; // 新的位置// 判断新的位置是否符合矩阵范围内并且没有访问过if (newX <= n - 1 && newY <= n - 1 && newX >= 0 && newY >= 0 && isV[newX][newY]!=1) {x = newX;y = newY;count++;nums[x][y] = count;isV[x][y] = 1;} else {// 到此步，说明走到头了，要改变方向d = (d + 1) % 4;}}return nums;}
};

看了别人的解法，有几个点可以注意下：

• vector<vector<int>> nums(n,vector<int>(n)); 这种定义会默认全部初始为0，而 int nums[4][4]; 则不会初始为0，需要手动初始化为0
• 二维数组 isV[n][n] 初始化为0时，不必使用双重 for 循环，可以用 int isV[n][n]={0}; 快速初始化
• while(1) 可以换成 while (count <= n * n)，这样就不用专门去判断 count 是否等于 n*n 然后 break 了

别人的解法

代码随想录中的解法有点复杂了，这里就不分析了，附上在 LeetCode 官方题解评论区下看到的一个不错的题解
来源：59. 螺旋矩阵 II 题解 - 力扣（LeetCode）

我的想法是定义一个方向数组，循环这个方向数组，并且还要用另一个数组记录每个位置是否已经访问过。而这个题解省去了方向数组和定义否访问过的数组的创建过程。直接用4个 for 循环代表4个方向，外层用 while 来判断是否填充到了最后一个位置。

代码中的 up、down、left、right 分别代表着当前需要填充区域的上下左右边界，在向前走一个方向要转弯的时候要改变一下边界的数值

class Solution {public:vector<vector<int>> generateMatrix(int n) {vector<vector<int>> res(n,vector<int>(n));// 分别代表着当前需要填充区域的上下左右边界int up = 0, down = n - 1, left = 0, right = n - 1, index = 1;while (index <= n * n) {// 从左向右赋值for (int i = left; i <= right; i++) {res[up][i] = index++;}up++; // 上面的一行赋值后上边界应该下移一行，下同// 从上向下赋值for (int i = up; i <= down; i++) {res[i][right] = index++;}right--;// 从右向左赋值for (int i = right; i >= left; i--) {res[down][i] = index++;}down--;// 从下向上赋值for (int i = down; i >= up; i--) {res[i][left] = index++;}left++;}return res;}
};

总结