基础算法C++讲解（目前更新至：双指针）

---

前言

该文简单讲解竞赛须知的基础算法，有新的想法欢迎在评论区里讨论。
目前更新至：双指针+滑动窗口，预计24.3.1更新二分查找算法。

---

一、双指针

常见的双指针有两种：一种是对撞指针（两端向中间移动）；一种是左右指针，也称快慢指针（两个指针以不同移动速度向同一方向移动）。

对撞指针常见于
快慢指针常见于：环形链表、数组等需要循环查找的情况。

下面将以两个例子分别讲解。

1.对撞指针：

leetocode_11.盛最多水的容器：https://leetcode.cn/problems/container-with-most-water/description/

解法一：暴力枚举（会超时）
枚举出所有容器并保存在一个新建数组中，找出其中容器最大的。
无法编译通过，故此处不编写代码。

解法二：对撞指针
构建左右指针left, right，分别从数组两边向中间移动，此时容器底宽为：right - left; 高为两边数组中小的一个：min(height[left],height[right)。

思路初始化完毕，下面考虑移动边界。
假设固定一边边界，移动另一边边界（此处举例固定右边边界，移动左边边界），宽度必定变小，此时有两种情况：

(1)假设左边高度小于右边高度：
此时容器高度由左边高度确定，
左边新移动的高度无法确定是否比之前左边高度高，故容器体积无法预测，因此有可能变大。
(2)假设左边高度大于右边高度：
此时容器高度由右边高度确定，
若左边新移动的高度高于右边高度，此时容器高度依旧由右边高度确定，底宽变小，高度不变容积变小；
若左边新移动的高度底于右边高度，此时容器高度由左边高度确定，底宽变小，高度变小，容积变小；

固定左边边界，移动右边边界同理。
由此舍去不必要的枚举过程（每次移动高的，固定低的），减少循环次数。

最后确定什么时候退出循环：当数组遍历完即left == right时退出。

综上，代码如下：

int maxArea(vector<int>& height) {
        int left = 0, right = height.size() - 1,ret = 0;
        while(left < right){
            int v = min(height[left], height[right]) * (right - left);
            ret = max(v,ret);
            if(height[left] < height[right])
                left++;
                else
                right--;
        }
        return ret;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

对撞指针相似题目：
leetcode_7.三数之和：https://leetcode.cn/problems/3sum/description/

2.快慢指针

leetcode_202.快乐数：https://leetcode.cn/problems/happy-number/description/

解法：快慢指针

题目说明对于一个数有两种情况：
(1)一直在1中死循环：1->1->1->…
(2)在历史中死循环，但是永远不为1.

现在需要知道，第二种情况死循环是否有范围。

证明：
题目已经说明数最大为2^31 - 1即21亿多，为10位数，取10位数最大位9999999999，
在经过该计算一次计算后即为10 * 9^2 = 810
之后每一次计算都不会在超出该值，因此始终在[1,810]中循环。

取最坏情况，即每种数字都被计算一遍，则811次必定循环。
因此可用快慢指针解决。

算法理论完毕，下面讲解如何计算n每位数的平方和：

//循环迭代下面步骤：
int t = n % 10;
n /= 10;
sum = sum + t * t;
//循环结束条件易得为n == 0 时
1
2
3
4
5

综上，代码可得：

	int bitSum(int n)
    {
        int sum = 0;
        while(n){
            int t = n % 10;
            sum += t*t;
            n /= 10;
        }
        return sum;
    }
    
    bool isHappy(int n) {
        int slow = n, fast = bitSum(n);
        while(slow != fast)
        {
            slow = bitSum(slow);
            fast = bitSum(bitSum(fast));

        }
        return slow == 1;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

二、滑动窗口

滑动窗口与双指针类似，但是区别在于滑动窗口是限定区间，区间内有指针辅助操作，且该限定区间可根据需要做相应的移动，而双指针的区间是整个范围（数组算法即整个数组）。
leetcode_904.水果成篮：https://leetcode.cn/problems/fruit-into-baskets/description/

因研究对象是一段连续区间，故可用滑动窗口解决该问题。

1.首先判断左出区间和右入区间的时机：
左区间固定，在右区间扫到第三种水果的时候停止扫描。
计算水果数量后，左侧区间陆续滑出，直至符合题意（水果数量不超过2），继续循环。

2.如何判断是否符合题意
使用哈希数组统计水果种类的数量，且可存储该水果共采摘几次。

3.右入区间后操作
新扫入的水果种类在哈希表中加一。

4.左出区间操作
左侧每扫出一个水果，则在对应的哈希表中减一，直至某一水果种类减为零。

5.长度判断
右侧扫入水果则加一，左侧扫出则减一，但每次仅记录最大值。

综上，代码如下：

int totalFruit(vector<int>& fruits) {
        unordered_map<int,int> hash;//建立hash表，题目中用数字代表水果种类，则此处记录方式使用int，第二个int记录该水果采摘几次
        int len = 0, n = fruits.size();
        for(int left = 0, right = 0; right < n ; right++)//遍历数组
        {
            hash[fruits[right]]++;//右侧扫入水果数量的hash表对应位置+1
            while(hash.size() > 2){//扫到第三种水果
                hash[fruits[left]]--;//左侧扫出的水果在hash表中对应位置-1
                if(hash[fruits[left]] == 0)    hash.erase(fruits[left]);//减为0是删除该种水果
                left++;
            }
            len = max(len, right - left + 1);//与上次长度作比较，每次记录最大值
        }
        return len;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

滑动窗口题目：
leetcode_1104.最大连续1的个数iii:https://leetcode.cn/problems/max-consecutive-ones-iii/description/

二分查找

总结

24.3.1预计更新二分查找。
后续可能更新前缀和，位运算、动态规划等算法，敬请期待。