算法(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)
            {
                //如果该元素是0
                pivot++;
                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;
            else
                right=mid;
        }
        if(x/left==left) return left;  //多一层判断，如果x正好是整数平方根存在返回left
        return 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;
            else
                right=mid;
        }
        return left;
        // 暴力解法
        // int i=0;
        // for(i=0;i<records.size();i++)
        // {
        //     if(i!=records[i])
        //     {
        //         return i;
        //     }
        // }
        // return i;
    }
};