企业官网建设流程全解析

数组

数组是存放在连续地址空间上的相同类型数据的集合。

数组中的元素可以方便地通过下表来索引。

数组下标从0开始。

C++中二维数组在地址空间上也是连续的，如下图：

二分查找

leetcode链接：704.二分查找

这道题目的前提是数组为有序数组，同时数组无重复元素，是二分法最基础的运用。

二分法的第一种写法：[left, right] (左闭右闭)

第一种写法中，我们每次查找的区间是一个左闭右闭的区间，target就在这个区间中，所以有如下两点：

• while(left <= right)要使用 <= ，因为left == right是有意义的，left == right时仍然需要遍历。
• if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1.

classSolution{public:intsearch(vector<int>&nums,inttarget){intleft=0;intright=nums.size()-1;while(left<=right){intmiddle=left+(right-left)/2;if(nums[middle]>target)right=middle-1;elseif(nums[middle]<target)left=middle+1;elsereturnmiddle;}return-1;}};

• 时间复杂度：O(log n)，空间复杂度：O(1)

二分法的第二种写法：[left, right) (左闭右开)

• while (left < right)，这里使用 < ,因为left == right在区间[left, right)是没有意义的。
• if (nums[middle] > target) right 更新为 middle，因为当前nums[middle]不等于target，去左区间继续寻找，而寻找区间是左闭右开区间，所以right更新为middle，即：下一个查询区间不会去比较nums[middle].

classSolution{public:intsearch(vector<int>&nums,inttarget){intleft=0;intright=nums.size();while(left<right){intmiddle=left+(right-left)/2;if(nums[middle]>target)right=middle;elseif(nums[middle]<target)left=middle+1;elsereturnmiddle;}return-1;}};

方法一和方法二在代码上的的主要三处区别：

leetcode题目链接：35.搜索插入位置

这道题目是上面的变式：当查找目标target不在数组中，应该按照原数组顺序返回它应该被插入的位置。

二分查找结束时的状态：

所以只需要在上一题的代码的基础上把return -1改成return left即可。

leetcode题目链接：34.在排序数组中查找元素的第一个和最后一个位置

本题目时在一个非递减数组nums中查找目标值target，但是目标值可能有多个，最后返回给定目标值在数组中的开始位置和结束位置。

寻找target在数组中的左右边界，有如下三种情况：

1. target 在数组范围的右边或者左边，例如数组{3, 4, 5}，target为2或者数组{3, 4, 5},target为6，此时应该返回{-1, -1}.
2. target 在数组范围中，且数组中不存在target，例如数组{3,6,7},target为5，此时应该返回{-1, -1}.
3. target 在数组范围中，且数组中存在target，例如数组{3,6,7},target为6，此时应该返回{1, 1}.

要写两个函数分别确定target的左边界LeftBorder和右边界RightBorder，并且计算出来的左边界和右边界是不包含target的边界。

classSolution{public:vector<int>searchRange(vector<int>&nums,inttarget){intleftborder=getLeftBorder(nums,target);intrightborder=getRightBorder(nums,target);// 情况一：target的值在数组范围之外if(leftborder==-2||rightborder==-2)return{-1,-1};// 情况三if(rightborder-leftborder>1)return{leftborder+1,rightborder-1};// 情况二return{-1,-1};}private:intgetRightBorder(vector<int>&nums,inttarget){intleft=0;intright=nums.size()-1;intrightborder=-2;while(left<=right){intmiddle=left+(right-left)/2;if(nums[middle]>target)right=middle-1;else{left=middle+1;rightborder=left;}}returnrightborder;}intgetLeftBorder(vector<int>&nums,inttarget){intleft=0;intright=nums.size()-1;intleftborder=-2;while(left<=right){intmiddle=left+(right-left)/2;if(nums[middle]<target)left=middle+1;else{right=middle-1;leftborder=right;}}returnleftborder;}};

leetcode题目链接：69.x的平方根

本题目要求计算一个非负整数 x 的算数平方根，返回类型是整数，小数部分将被舍去，不允许使用内置的函数和算符，0 <= x <= 2³¹- 1.

此题最需要注意的点是防止数据溢出(使用if(mid <= x / mid)而不是if(mid * mid <= x)，由于程序所求的算数平方根可能小于其真实值，所以需要使答案先假定为一个偏小的可能值，再往右找更大值。

classSolution{public:intmySqrt(intx){if(x<2)returnx;intleft=1,right=x/2;intans=0;while(left<=right){intmid=left+(right-left)/2;if(mid<=x/mid){ans=mid;// 记录当前可能答案left=mid+1;// 继续往右找更大值}else{right=mid-1;}}returnans;}};

双指针法

快慢指针

leetcode题目链接：27.移除元素

题目给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。**数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。**所以，本题目不需要考虑数组中超出新长度后面的元素。

本题的暴力解法是使用两层 for 循环，第一层 for 循环用来遍历整个数组，删除 val，第二个 for 循环把每个被删除元素的后面的元素提前。这个方法的时间复杂度是 O(n²)，空间复杂度是 O(1)。更好的方法是双指针法。

双指针法就是在数组、字符串、链表等线性结构中，使用两个变量（通常用fast和slow）表示两个位置，通过移动这两个位置来完成遍历、查找、删除、合并等操作。它的核心思想是，通过两个指针协同移动，避免用一层循环从头扫到尾，再另一层循环查找，从而把时间复杂度从 O(n²)降到 O(n)。

// 时间复杂度：O(n)// 空间复杂度：O(1)classSolution{public:intremoveElement(vector<int>&nums,intval){intslowIndex=0;for(intfastIndex=0;fastIndex<nums.size();fastIndex++){if(val!=nums[fastIndex]){nums[slowIndex++]=nums[fastIndex];}}returnslowIndex;}};

左右指针

leetcode题目链接：977.有序数组的平方

这道题的最优做法是双指针法，因为数组已经有序，所以平方后的最大值一定出现在数组两端之一，所以只需要开一个新的数组存放结果，然后定义左右双指针，分别从两边开始向中间扫描，将左右指针平方后的较大的数放入结果数组即可。

classSolution{public:vector<int>sortedSquares(vector<int>&nums){intn=nums.size();vector<int>result(n);intleft=0;intright=n-1;intpos=n-1;while(left<=right){// 注意此处小于等于，因为要处理最后一个数intleftSquare=nums[left]*nums[left];intrightSquare=nums[right]*nums[right];if(leftSquare>rightSquare){result[pos--]=leftSquare;left++;}else{result[pos--]=rightSquare;right--;}}returnresult;}};

滑动窗口

leetcode题目链接：209.长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

classSolution{public:intminSubArrayLen(ints,vector<int>&nums){intresult=INT32_MAX;intsum=0;// 滑动窗口数值之和intleft=0;// 滑动窗口起始位置intsubLength=0;// 滑动窗口的长度for(intright=0;right<nums.size();right++){sum+=nums[right];// 注意这里使用while，每次更新 left（起始位置），并不断比较子序列是否符合条件while(sum>=s){subLength=(right-left+1);// 取子序列的长度result=result<subLength?result:subLength;sum-=nums[left++];// 这里体现出滑动窗口的精髓之处，不断变更i（子序列的起始位置）}}// 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列returnresult==INT32_MAX?0:result;}};

滑动窗口法的本质是：用 left 和 right 维护一个连续区间，通过右端扩张、左端收缩，使窗口始终朝着目标状态移动，从而避免重复枚举所有子数组或子串。

滑动窗口的核心过程：

1. right 向右扩张窗口
2. 当窗口不满足条件或已经满足条件时，left 向右收缩窗口
3. 在过程中更新答案

滑动窗口最常见的模板

intleft=0;for(intright=0;right<nums.size();right++){// 1. 把 nums[right] 加入窗口while(窗口需要收缩){// 2. 移除 nums[left]left++;}// 3. 更新答案}

滑动窗口最重要的三个问题：

1. 窗口里维护什么？
2. 什么时候扩大窗口？（通常是每次循环都扩大，所以主循环的循环变量是右边界 right）
3. 什么时候缩小窗口？

leetcode题目链接：904.水果成篮

这是一道经典的滑动窗口问题，使用的方法是滑动窗口 + 哈希表。

关键在于，怎样想到使用滑动窗口？

答案是，本题目有几个明显特征：1. 要找的是连续的一段果树；2. 要求这段区间中最多只有两种水果；3. 要求最大长度。

classSolution{public:inttotalFruit(vector<int>&fruits){unordered_map<int,int>count;intleft=0;intans=0;for(intright=0;right<fruits.size();right++){count[fruits[right]]++;while(count.size()>2){count[fruits[left]]--;if(count[fruits[left]]==0){count.erase(fruits[left]);}left++;}ans=max(ans,right-left+1);}returnans;}};

leetcode题目链接：76.最小覆盖子串

这道题目要求我们在字符串 s 中找一个最短的连续子串，使它包含字符串 t 中的所有字符，并且重复字符也要满足数量要求。

classSolution{public:stringminWindow(string s,string t){unordered_map<char,int>need;unordered_map<char,int>Window;for(charc:t)need[c]++;intleft=0;intvalid=0;intstart=0;intlen=INT_MAX;for(intright=0;right<s.size();right++){charc=s[right];if(need.count(c)){Window[c]++;if(Window[c]==need[c])valid++;}while(valid==need.size()){if(right-left+1<len){start=left;len=right-left+1;}chard=s[left];if(need.count(d)){if(Window[d]==need[d]){valid--;}Window[d]--;}left++;}}returnlen==INT_MAX?"":s.substr(start,len);}};

前缀和

前缀和是一种用于快速计算区间和的算法思想。

假设有数组：

nums = [2, 4, 1, 5, 3]

普通求区间[1, 3]的和，需要计算：

nums[1] + nums[2] + nums[3] = 4 + 1 + 5 = 10

如果有很多次区间求和，每次都重新遍历，会比较慢。

前缀和的做法是：提前构造一个数组prefix，其中：

prefix[i]表示nums[0]到nums[i - 1]的元素和

注意这里常用长度为n + 1的前缀和数组。

例如：

nums = [2, 4, 1, 5, 3]

构造：

prefix[0] = 0 prefix[1] = nums[0] = 2 prefix[2] = nums[0] + nums[1] = 6 prefix[3] = nums[0] + nums[1] + nums[2] = 7 prefix[4] = nums[0] + nums[1] + nums[2] + nums[3] = 12 prefix[5] = nums[0] + nums[1] + nums[2] + nums[3] + nums[4] = 15

所以：

prefix = [0, 2, 6, 7, 12, 15]

前缀和的核心公式

nums[left] + nums[left + 1] + ... + nums[right] = prefix[right + 1] - prefix[left];

前缀和数组prefix通常开 n + 1，推荐写成：

vector<int>prefix(n+1,0);for(inti=0;i<n;i++){prefix[i+1]=prefix[i]+nums[i];}

这样的好处是：可以统一处理下标 0 开始的区间，可以地适配上面的公式。

前缀和适合解决如下问题：

1. 连续子数组的和
2. 多次查询区间和
3. 子数组和等于 k（前缀和 + 哈希表）leetcode题目链接：560.和为K的子数组
4. 矩阵区域和（二维前缀和）
5. 区间加减操作（差分数组）
6. 求中心下表 / 左右和相等（前缀和思想）leetcode题目链接：724.寻找数组的中心下标

二维前缀和

二维前缀和prefix[i][j]表示 从matrix[0][0]到matrix[i - 1][j - 1]这个矩形区域的和.

通常也使用多开一行一列的写法：

vector<vector<int>> prefix(m + 1, vector<int>(n + 1, 0));

二维前缀和的构造公式

prefix[i][j] = prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1] + matrix[i - 1][j - 1];

二维前缀和的查询公式

假如要查询矩阵中从(row1, col1)到(row2, col2)的矩形区域和，用

prefix[row2 + 1][col2 + 1] - prefix[row1][col2 + 1] - prefix[row2 + 1][col1] + prefix[row1][col1]

代码：

classNumMatrix{private:vector<vector<int>>prefix;public:NumMatrix(vector<vector<int>>&matrix){intm=matrix.size();intn=matrix[0].size();prefix.resize(m+1,vector<int>(n+1,0));for(inti=1;i<=m;i++){for(intj=1;j<=n;j++){prefix[i][j]=prefix[i-1][j]+prefix[i][j-1]-prefix[i-1][j-1]+matrix[i-1][j-1];}}}intsumRegion(introw1,intcol1,introw2,intcol2){returnprefix[row2+1][col2+1]-prefix[row1][col2+1]-prefix[row2+1][col1]+prefix[row1][col1];}};

前缀和 与 差分数组 是一对相反操作。前者常用于快速查询区间和，后者常用于快速进行区间加减.