算法(C++实现)

从现在开始，开辟一个新的专题----算法，这篇文章介绍双指针，滑动窗口，二分查找这几种算法以及附有相应的练习题。

1.双指针

常见的双指针形式有两种，一种是对撞指针，一种是同向双指针。下面是三种对应情况

（1）对撞指针的两端指针向中间移动，结束条件一般是两边指针相遇，而对撞双指针通常是需要利用区间单调性决定移动左边还是右边。（问题1.4，1.5）

（2）同向双指针中的快慢指针（问题1.3）让两个指针以不同的速度移动，它不仅可以处理环形链表的问题，更是一种思想，解决循环往复的问题，这类问题可能结束条件不好判断，可以考虑快慢指针。

（3）同向双指针中以一个遍历指针，另一个指针在不同情况下指向不同的移动操作，也可以用于作为一个分割指针，使得该指针两边的元素性质不同。（问题1.1，1.2）

1.1 283. 移动零 - 力扣（LeetCode）

给定⼀个数组 nums ，编写⼀个函数将所有0移动到数组的末尾，同时保持⾮零元素的相对顺序。

请注意，必须在不复制数组的情况下原地对数组进⾏操作。

示例:

输⼊:nums = [0,1,0,3,12] 输出:[1,3,12,0,0]

思路：情况（3）的思路，一个分隔指针从数组-1的位置开始，它前面的位置均是非零元素，如果遍历指针指向元素是零，遍历指针++，分割指针不动，如果遍历指针指向元素是非0，分割指针++，交换两个指针指向的值，遍历指针++，当遍历到数组末尾时，循环结束。

class Solution {
public:void moveZeroes(vector<int>& nums) {// pivot 指向最后一个非0元素int pivot=-1;for(auto &x:nums){if(x!=0){//如果该元素是0pivot++;swap(x,nums[pivot]);}}}
};

1.2 1089. 复写零 - 力扣（LeetCode）

给你一个长度固定的整数数组 arr ，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。

注意：请不要在超过该数组长度的位置写入元素。请对输入的数组就地进行上述修改，不要从函数返回任何东西。

示例 1：

输入：arr = [1,0,2,3,0,4,5,0]
输出：[1,0,0,2,3,0,0,4]
解释：调用函数后，输入的数组将被修改为：[1,0,0,2,3,0,0,4]

思路：这个题目要采取两个同向双指针去完成。

第一步要找到开始复写的位置，如示例中的4的位置，这个采取cur走一步，dest在cur为0时走两步，cur为非零元素时走一步的方式。

第二步就是处理边界情况，因为可能最后一个复写的元素是0，dest就超过了数组最大长度

第三步也是同向双指针，将cur位置的元素给dest位置的元素，如果是非0，之间赋值即可，如果是0则dest和dest-1的值全都赋值为0，同时dest向前走两步。

class Solution
{public:void duplicateZeros(vector<int>& arr){// 1. 先找到最后⼀个数int cur = 0, dest = -1, n = arr.size();while(cur < n){if(arr[cur]) dest++;else dest += 2;if(dest >= n - 1) break;cur++;}// 2. 处理⼀下边界情况if(dest == n){arr[n - 1] = 0;cur--; dest -=2;}// 3. 从后向前完成复写操作while(cur >= 0){if(arr[cur]) arr[dest--] = arr[cur--];else{arr[dest--] = 0;arr[dest--] = 0;cur--;}}}
};

1.3 202. 快乐数 - 力扣（LeetCode）

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
如果这个过程 结果为 1，那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

示例 1：

输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

思路：使用快慢指针，就是在⼀个圆圈中，快指针总是会追上慢指针的，也就是说他们总会相遇在⼀个位置上。我们把操作即为bitsum，执行该操作之后，数字变化一次，快指针一次执行两次操作，慢指针一次执行一次，它们必定会相遇，如果相遇位置slow或者fast的值是1 ，那么这个数⼀定是快乐数，否则就不是快乐数。

1.4 11. 盛最多水的容器 - 力扣（LeetCode）

思路1：暴力求解，思路：枚举出能构成的所有容器，找出其中容积最⼤的值。采取两个指针i，j分别指向容器左端和右端，j不懂，i依次向右移动到j-1的位置，求出每一次的容积，然后j到j-1的位置，然后i依次向右移动到j-2的位置，求出每一次的容积，取所有容积的最大值。（超时）

思路2：在暴力求解上优化，如果左边界高度小于右边界高度，只需要移动左边界即可，反之只需要移动右边界

class Solution {
public:int maxArea(vector<int>& height) {if(height.size()<=1){return 0;}int left=0;int right=height.size()-1;vector<int> maxArray;   //也可以不需要数组while(left<right){int w=right-left;int h=min(height[left],height[right]);int s=w*h;maxArray.push_back(s);if(height[left]<=height[right]){left++;}else{right--;}}int ret=0;for(int i=0;i<maxArray.size();i++){if(maxArray[i]>ret){ret=maxArray[i];}}return ret;}
};

1.5 611. 有效三角形的个数 - 力扣（LeetCode）

给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。

示例 1:

输入: nums = [2,2,3,4]
输出: 3
解释:有效的组合是: 
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3

解法1：三层for循环枚举出所有的三元组，并且判断是否能构成三⻆形。虽然说是暴⼒求解，但是还是想优化⼀下，如果能构成三⻆形，需要满⾜任意两边之和要⼤于第三边。但是实际上只需让较⼩的两条边之和⼤于第三边即可。因此我们可以先将原数组排序，然后从⼩到⼤枚举三元组，⼀⽅⾯省去枚举的数量，另⼀⽅⾯⽅便判断是否能构成三角形。（超时）

解法2：排序+对撞双指针。固定最长边i，区间 [left, right] i位置左边的区间（也就是比它小的区)

如果nums[left] + nums[right] > nums[i] :说明 [left, right - 1] 区间上的所有元素均可与 nums[right] 构成比nums[i] ⼤的⼆元组，满⾜条件的有right - left 种，right--

如果nums[left] + nums[right] <= nums[i] ：说明left 位置的元素是不可能与 [left + 1, right] 位置上的元素构成满⾜条件的⼆元组 left 位置的元素可以舍去，left++

class Solution {
public:
// 利用单调性，可以做双指针算法，指针可以指的是一个数字int triangleNumber(vector<int>& nums) {sort(nums.begin(),nums.end());int count=0;for(int i=0;i<nums.size();i++){for(int j=i+1;j<nums.size();j++){for(int k=j+1;k<nums.size();k++){//如果可以构成三角形，count++；if(nums[i]+nums[j]>nums[k]){count++;}}}}return count;}
};

1.6 15. 三数之和 - 力扣（LeetCode）

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

思路1：暴力，三重for循环，i,j,k三个指针开始时分别指向0，1，2三个位置，然后往后遍历所有三元组，符合情况放到一个vector容器当中。

思路2：先排序，然后固定⼀个数a ，在这个数后⾯的区间内，使用对撞双指针算法快速找到两个数之和等于-a 即可。但是要注意的是，这道题⾥⾯需要有去重操作，找到⼀个结果之后， left 和right 指针要跳过重复的元素；当使⽤完⼀次双指针算法之后，固定的a 也要跳过重复的元素。

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {sort(nums.begin(),nums.end());vector<vector<int>> ret;for(int end=nums.size()-1;end>=2;end --){int left=0;int right=end -1;while(left<right){if(nums[left]+nums[right]+nums[end]==0){vector<int> v;  // 每次都会定义一遍v.push_back(nums[left]);v.push_back(nums[right]);v.push_back(nums[end]);ret.push_back({nums[left],nums[right],nums[end]});//用数组构造v，两种写法都可以left++;right--;   //找到一个结果之后，继续循环找//处理去重while(left<right&&nums[left]==nums[left-1]){left++;}}else if(nums[left]+nums[right]+nums[end]>0){right--;}else{left++;}}while(end>=2&&nums[end]==nums[end-1]){end--;}}// vector<vector<int>> vec(ret);// std::sort(vec.begin(), vec.end());unique()会把重复数据放在 容器末尾// vec.erase(std::unique(vec.begin(), vec.end()), vec.end()); //ret.earse(unique(ret.begin(),ret.end()),ret.end());return ret;}
};

其中四数之和和两数之和与之类似。

18. 四数之和 - 力扣（LeetCode）四数之和思路依次固定⼀个数 a ，在这个数a 的后面区间上，在a+1位置固定数b，再利用两数之和获取两个指针，使这两个数的和等于target- a-b 即可。

2.滑动窗口

滑动窗口可以看成一个特殊的同向双指针，它主要用来处理连续子数组，连续字符串问题。其主要就是三步：进窗口，判断，出窗口，更新结果，更新结果可能在判断时更新，也可能在出窗口时候更新。

2.1 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] 是该条件下的长度最小的子数组。

思路：滑动窗口，right指针不断向后走直到最后一个元素，当sum>=target时，我们需要出窗口加更新结果，此时left指针不断向前走，同时ret为窗口长度的最小值。

2.2 3. 无重复字符的最长子串 - 力扣（LeetCode）

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"所以其长度为 3。

思路：hash表加滑动窗口，每个right指针指向的元素都进入窗口，然后hash表来判断进入窗口的元素是否与前面元素重复，如果重复，则一直将left指向元素出窗口直到窗口内无重复元素，最后更新结果。

class Solution {
public:int lengthOfLongestSubstring(string s) {int ret=0;int hash[128]={0};for(int left,right=0;right<s.size();right++){//进入窗口hash[s[right]]++;//出窗口while(hash[s[right]]>1&&left<right){hash[s[left]]--;left++;}//更新结果ret=max(ret,right-left+1);}return ret;}
};

2.3 1004. 最大连续1的个数 III - 力扣（LeetCode）

思路：该题维护一个合法窗口，使得里面0的数量小于k,我们可以使用一个变量zero统计窗口内0的数量，在窗口内只需要将其维护好即可。

class Solution {
public:int longestOnes(vector<int>& nums, int k) {int ret=0;for(int left=0,right=0,zero=0;right<nums.size();right++){//进窗口if(nums[right]==0) zero++;while(zero>k){if(nums[left]==0) zero--;left++;}ret=max(ret,right-left+1);}return ret;}
};

2.4 1658. 将 x 减到 0 的最小操作数 - 力扣（LeetCode）

给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，需要修改数组以供接下来的操作使用。

如果可以将 x 恰好减到 0 ，返回 最小操作数 ；否则，返回 -1 。

示例 1：

输入：nums = [1,1,4,2,3], x = 5
输出：2
解释：最佳解决方案是移除后两个元素，将 x 减到 0 。

求一个连续窗口内值的和为target，其中target = sum(nums) - x 。如果target < 0 ，问题⽆解；初始化左右指针 l = 0 ,r = 0，r 指向元素进入窗口,记录当前滑动窗内数组元素和n，如果n>sum,则左边元素不断出窗口。如果n==target，则记录当前满足条件数组的最⼤区间⻓度maxLen = -1 。

class Solution {public:int minOperations(vector<int>& nums, int x) {int sum=0;for(auto &e:nums){sum+=e;}if(sum<x) return -1;int ret=-1;   //窗口长度int target=sum-x;for(int left=0,right=0,n=0 ;right<nums.size();right++){//进窗口n+=nums[right];while(n>target){n-=nums[left];left++;}if(n==target)ret= max(right-left+1,ret);}//进窗口 判断 出窗口return ret==-1?-1:nums.size()-ret;}
};

2.4 438. 找到字符串中所有字母异位词 - 力扣（LeetCode）

因为字符串p 的异位词的⻓度⼀定与字符串 p 的⻓度相同，所以我们可以在字符串s 中构造⼀个⻓度为与字符串p 的⻓度相同的滑动窗⼝，并在滑动中维护窗⼝中每种字⺟的数量；当窗⼝中每种字⺟的数量与字符串p 每种字⺟的数量相同时，则说明当前窗⼝为字符串 p的异位词。

class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> ret;int hash1[26]={0};int hash2[26]={0};for(int i=0;i<p.size();i++){hash1[p[i]-'a']++;}for(int left=0,right=0,count=0;right<s.size();right++){//进入窗口hash2[s[right]-'a']++;//维护count ，即有效字符的个数if(hash2[s[right]-'a']<=hash1[s[right]-'a']){count++;}//判断 什么时候left需要向右移动if(right - left + 1 > p.size()){//进入的是无效字符,count--if(hash2[s[left]-'a']<=hash1[s[left]-'a'])  {count--;}hash2[s[left]-'a']--;left++;}//判断条件是 count和大小相等，并没有考虑窗口的大小if(count==p.size()){ret.push_back(left);}}return ret;}
};

3.二分查找

它是O(logn)的算法，或者递增(非递减)序列，如果出现这样的字眼，考虑二分查找。

普通的二分查找，找一个值，while(left<=right)，大于小于两种情况下对应left和mid分别不同的移动，如果相等，则找到了，则返回该值即可。

边界查找：当某个元素的左边（或右边）严格满足某种性质时，可以用二分查找解决该题，结束条件是while(left<right)

二分查找左边界：mid取左值，同时判断情况是这个数小于target时，左边所有值全部排除

二分查找右边界：mid取右值，同时判断情况是这个数大于target时，右边所有值全部排除

3.1 704. 二分查找 - 力扣（LeetCode）

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

class Solution {
public:int search(vector<int>& nums, int target) {//暴力解法每次干掉一个数字int ret=-1;int left=0;int right=nums.size()-1;while(left<=right){// 数组有二段性，摒除一个区间的数字int mid=(left+right)/2;if(nums[mid]<target){left=mid+1;}else if(nums[mid]>target){right=mid-1;}else{ret=mid;break;}}return ret;}
};

3.2 34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {if(nums.size()==0){return {-1,-1};}int leftret=-1;int rightret=-1;int left=0;int right=nums.size()-1;//寻找左边界while(left<right){int mid=left+(right-left)/2;  //当两个数时，取左边值if(nums[mid]<target)          // mid左边所有值全部排除，在[mid+1,right]找左边界left=mid+1;else right=mid;}//此时left==mid等于左边界if(nums[left]==target){leftret=left;}right=nums.size()-1;//寻找右边界while(left<right){int mid=left+(right-left+1)/2;if(nums[mid]>target)right=mid-1;else left=mid;}if(nums[right]==target){rightret=right;}return {leftret,rightret};}
};

3.2 35. 搜索插入位置 - 力扣（LeetCode）

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2

思路：找到插入目标值的左边界，如果左边界等于target，则返回左边界（左边所有值都是小于nums[left]），如果该值小于left，证明这个区间所有值都是小于target，它插入数组最后一个位置，返回left+1。

class Solution {
public:int searchInsert(vector<int>& nums, int target) {//寻找左右边界，如果相等则返回//右边界int left=0;int right=nums.size()-1;while(left<right){int mid=left+(right-left)/2;if(nums[mid] < target) left = mid + 1;else{right=mid;}}if(nums[left]<target){return left+1;}return left;}
};

3.3 69. x 的平方根 - 力扣（LeetCode）

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1：

输入：x = 4
输出：2

在一段区间内，分析左右两边元素的特征，假设index即为x的算术平方根则

▪ [0, index] 之间的元素，平⽅之后都是⼩于等于x 的；

▪ [index + 1, x] 之间的元素，平⽅之后都是⼤于 x 的。因此此题目选用找右边界的解法比较好，但是本人采用左边界做法，此时需要多加一层结果的判断。

class Solution {
public:int mySqrt(int x) {//一个数字，左边平方比它大，右边平方比他小//找到左边界if(x<1) return 0;int left=1;int right=x;while(left<right){long long mid=left+(right-left)/2;if(mid*mid<x) left=mid+1;elseright=mid;}if(x/left==left) return left;  //多一层判断，如果x正好是整数平方根存在返回leftreturn left-1;}
};

3.4 852. 山脉数组的峰顶索引 - 力扣（LeetCode）

给定一个长度为 n 的整数山脉数组 arr ，其中的值递增到一个 峰值元素 然后递减。

返回峰值元素的下标。

你必须设计并实现时间复杂度为 O(log(n)) 的解决方案。

示例 1：

输入：arr = [0,1,0]
输出：1

思路：找左边界即可。如果 mid位置呈现上升趋势，即arr[mid] > arr[mid - 1]，说明我们接下来要在 [mid + 1, right] 区间继续搜索；

class Solution {
public:int peakIndexInMountainArray(vector<int>& arr) {//采取寻找左边界的方式int left=1;int right=arr.size()-2;while(left<right){int mid=left+(right-left)/2;if(arr[mid]<arr[mid+1])  left=mid+1;           //上升数据else right=mid;}return left;}
};

3.5 LCR 173. 点名 - 力扣（LeetCode）

某班级 n 位同学的学号为 0 ~ n-1。点名结果记录于升序数组 records。假定仅有一位同学缺席，请返回他的学号。

示例 1:

输入: records = [0,1,2,3,5]
输出: 4

思路：利用性质的两端性，在该元素左边，i和nums[i]严格相等，因此可以采用寻找左边边界的方法求解。

class Solution {
public:int takeAttendance(vector<int>& records) {int left=0;int right=records.size();while(left<right){int mid=left+(right-left)/2;if(mid==records[mid])  //该元素左边严格满足mid=nums[mid] left=mid+1;elseright=mid;}return left;// 暴力解法// int i=0;// for(i=0;i<records.size();i++)// {//     if(i!=records[i])//     {//         return i;//     }// }// return i;}
};