数组算法分享 | 代码随想录(CPP+LeetCode)
总览
- [704. 二分查找](https://leetcode.cn/problems/binary-search/)
- [27. 移除元素](https://leetcode.cn/problems/remove-element/)
- [977. 有序数组的平方](https://leetcode.cn/problems/squares-of-a-sorted-array/)
- [209. 长度最小的子数组](https://leetcode.cn/problems/minimum-size-subarray-sum/)
- [59. 螺旋矩阵 II](https://leetcode.cn/problems/spiral-matrix-ii/)
- C++ Vector 使用指南
- 一维 Vector（动态数组）
- 基本概念
- 常见用法
- 二维 Vector（矩阵）
- 1️⃣ 声明和初始化二维 Vector
- 2️⃣ 访问和修改元素
- 3️⃣ 遍历二维 Vector
后面有 C++ 中 vector 一维、二维数组的使用说明
704. 二分查找
给定一个n个元素有序的（升序）整型数组nums和一个目标值target，写一个函数搜索nums中的target，如果target存在返回下标，否则返回-1。
你必须编写一个具有O(log n)时间复杂度的算法。
classSolution{public:intsearch(vector<int>&nums,inttarget){intleft=0;intright=nums.size()-1;while(left<=right){intmid=left+(right-left)/2;// 防止溢出if(nums[mid]==target){returnmid;// 找到目标，返回索引}elseif(nums[mid]<target){left=mid+1;// 目标在右半部分}else{right=mid-1;// 目标在左半部分}}return-1;// 未找到目标}};27. 移除元素
给你一个数组nums和一个值val，你需要原地移除所有数值等于val的元素。元素的顺序可能发生改变。然后返回nums中与val不同的元素的数量。
假设nums中不等于val的元素数量为k，要通过此题，您需要执行以下操作：
- 更改
nums数组，使nums的前k个元素包含不等于val的元素。nums的其余元素和nums的大小并不重要。 - 返回
k。
classSolution{public:intremoveElement(vector<int>&nums,intval){intslow=0;for(intfast=0;fast<nums.size();fast++){if(nums[fast]!=val){nums[slow++]=nums[fast];}}returnslow;}};977. 有序数组的平方
给你一个按非递减顺序排序的整数数组nums，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。
classSolution{public:vector<int>sortedSquares(vector<int>&nums){intk=nums.size()-1;vector<int>res(k+1);intright=k;intleft=0;while(k!=-1){intleftsquare=nums[left]*nums[left];intrightsquare=nums[right]*nums[right];if(leftsquare>rightsquare){res[k--]=leftsquare;left++;}else{res[k--]=rightsquare;right--;}}returnres;}};209. 长度最小的子数组
给定一个含有n个正整数的数组和一个正整数target。
找出该数组中满足其总和大于等于target的长度最小的子数组[nums[l], nums[l+1], ..., nums[r-1], nums[r]]，并返回其长度。如果不存在符合条件的子数组，返回0。
classSolution{public:intminSubArrayLen(inttarget,vector<int>&nums){inti=0;intsum=0;intres=nums.size()+1;for(intj=0;j<nums.size();j++){sum+=nums[j];while(sum>=target){intlen=j-i+1;res=(len<res)?len:res;sum-=nums[i];i++;}}if(res==(nums.size()+1))return0;elsereturnres;}};59. 螺旋矩阵 II
给你一个正整数n，生成一个包含1到n²所有元素，且元素按顺时针顺序螺旋排列的n x n正方形矩阵matrix。
classSolution{public:vector<vector<int>>generateMatrix(intn){vector<vector<int>>matrix(n,vector<int>(n,0));inttop=0,bottom=n-1;intleft=0,right=n-1;intnum=1;while(top<=bottom&&left<=right){for(intcol=left;col<=right;col++){matrix[top][col]=num++;}top++;for(introw=top;row<=bottom;row++){matrix[row][right]=num++;}right--;if(top<=bottom){for(intcol=right;col>=left;col--){matrix[bottom][col]=num++;}bottom--;}if(left<=right){for(introw=bottom;row>=top;row--){matrix[row][left]=num++;}left++;}}returnmatrix;}};C++ Vector 使用指南
一维 Vector（动态数组）
vector<int>是C++标准库中的动态数组容器，用来存储整数。
基本概念
- vector：来自
<vector>头文件，是一个模板类 - ：表示存储整数类型的元素
- 可以像数组一样使用，但大小可以动态增长
常见用法
#include<vector>usingnamespacestd;// 声明和初始化vector<int>nums={-1,0,3,5,9,12};// 创建并初始化vector<int>arr(5);// 创建大小为5的向量// 访问元素intfirst=nums[0];// 访问第一个元素intsize=nums.size();// 获取大小// 添加元素nums.push_back(15);// 在末尾添加元素// 遍历for(inti=0;i<nums.size();i++){cout<<nums[i]<<" ";}二维 Vector（矩阵）
1️⃣ 声明和初始化二维 Vector
// 方式1：声明空的二维 vectorvector<vector<int>>matrix;// 方式2：创建 n x n 的二维 vector，所有元素初始化为0vector<vector<int>>matrix(n,vector<int>(n,0));// 方式3：创建 m x n 的矩阵，初始化为特定值vector<vector<int>>matrix(m,vector<int>(n,5));// m行 n列，都是52️⃣ 访问和修改元素
vector<vector<int>>matrix(3,vector<int>(3,0));// 访问元素intvalue=matrix[0][1];// 第0行，第1列// 修改元素matrix[0][1]=10;// 动态添加行matrix.push_back(vector<int>{1,2,3});// 在某行添加列matrix[0].push_back(4);3️⃣ 遍历二维 Vector
// 方式1：使用索引for(inti=0;i<matrix.size();i++){for(intj=0;j<matrix[i].size();j++){cout<<matrix[i][j];}}// 方式2：使用范围for循环for(auto&row:matrix){for(intval:row){cout<<val;}}