【基础算法总结】双指针

算法原理：

我们也是定义两个变量 cur 和 dest，根据上面介绍的两个指针的位置，初始化 cur = 0, dest = -1。

在 cur 从前往后遍历的过程中，无非两种情况：
1. 遇到0元素：cur++
2. 遇到非0元素：先swap(dest+1, cur), 再cur++, dest++

代码实现：

class Solution 
{
public:
    void moveZeroes(vector<int>& nums) 
    {
        for(int cur = 0, dest = -1; cur < nums.size(); )
        {
            if(nums[cur] == 0) cur++;
            else swap(nums[dest+1], nums[cur]), cur++, dest++;
        }
    }
};

算法原理：

这道题看起来简单，但是有很多坑，很多细节。我们使用双指针先在草稿纸上模拟，不难发现从前往后复写是不行的，会覆盖后面的数据。但是要如何从后往前复写呢，起始位置怎么确定？

所以解决这个题有两个步骤：

1. 先找到最后一个复写的数。
这一步骤也要用双指针算法：

当走完这个双指针，此时 cur 指向的数就是最后一个要复写的数，dest 指向的位置就是开始复写的第一个位置。
2. 再从后往前进行复写操作：
在 cur 从后往前遍历的过程中，无非两种情况：
(1) 遇到0元素：dest向前复写两个0,cur–,dest -= 2
(2) 遇到非0元素：先arr[dest] = arr[cur], 再cur++, dest++

细节/技巧问题：

(1) 在第一步的第三小步中，一定要先判断 dest 是否已经结束
(2) 还要处理一种特殊情况：[1,0,2,3,0,4]。根据第一步的双指针，此时dest会越界，就要做特殊处理，当 dest == n 时，直接把 arr[n-1] = 0, cur–, dest -= 2。

代码实现：

class Solution
{
public:
    void duplicateZeros(vector<int>& arr)
    {
        // 找到最后一个要复写的位置
        int cur = 0, dest = -1, n = arr.size();
        while (cur < n)
        {
            if (arr[cur]) dest++;
            else dest += 2;

            if (dest >= n - 1) break;
            cur++; // 注意每次++之前都要先判断dest是否越界
        }

        // 处理特殊情况
        if (dest == n) arr[n - 1] = 0, cur--, dest -= 2;

        // 从后往前开始复写操作
        while (cur >= 0)
        {
            if (arr[cur]) arr[dest--] = arr[cur--];
            else
            {
                arr[dest] = 0, arr[dest - 1] = 0;
                dest -= 2;
                cur--;
            }
        }
    }
};

下面是一开始我写的错误代码，以示警戒：

class Solution
{
public:
    void duplicateZeros(vector<int>& arr)
    {
        // 先找到最后一个要复写的数
        int n = arr.size();
        int cur = 0, dest = -1;
        for (; dest < n - 1;)
        {
            if (arr[cur] != 0) dest++;
            else dest += 2;

            if (dest != n - 1)
                cur++;
        }

        // 处理边界情况
        if (dest == n) arr[n - 1] = 0, cur--, dest -= 2;

        // 从后往前完成复写操作
        for (; cur >= 0 && dest >= 0; )
        {
            if (arr[cur] != 0) arr[dest] = arr[cur], dest--;
            else arr[dest] = 0, arr[dest - 1] = 0, dest -= 2;

            cur--;
        }
    }
};

算法原理：

首先来理解题目：

所以这道题可以抽象成另类的 “链表是否带环问题”。只不过这道题是一定带环的，只要根据环内的数进行判断即可。

使用经典的快慢双指针算法：
(1) 定义快慢指针
(2) 慢指针每次向后走一步，快指针向后走两步
(3) 判断相遇时候的值即可

拓展：为什么这个题一定成环？

使用鸽巢原理证明。

细节/技巧问题：

(1) 这题的双指针不再是数组下标，而是一个数。
(2) 在进入第一次循环时，先让 fast 指向第二个数，不然进不了循环。

代码实现：

class Solution 
{
public:
    bool isHappy(int n) 
    {
        int slow = n, fast = mypow(n);
        while(slow != fast)
        {
            slow = mypow(slow);
            fast = mypow(mypow(fast));
        }
        if(slow == 1)
            return true;
        else
            return false;
    }

    int mypow(int n)
    {
        int sum = 0;
        while(n)
        {
            int a = n % 10;
            n /= 10;
            sum += a*a;
        }
        return sum;
    }
};

算法原理：

解法1：暴力枚举，O(N*N)。这应该是大家心中第一个闪过的想法，就是使用两层for循环计算出全部体积，再求出最大值。但是这个解法超时。

解法2：利用单调性，使用双指针，O(N)
首先观察一个规律：
我们固定一个数，再向外枚举，会出现下面的情况，结果都是缩小，就可以把这个数直接抹去，避免无用枚举。

所以可以把这个规律推广到全部数据：

定义两个指针指向开头和结尾，此时可以计算出一个体积，根据上面的规律把较小的那个高度直接舍去，指针向里缩，继续计算体积…，直到两个指针相遇，统计出最大体积。

细节/技巧问题：

体积= 高度 * 宽度。根据木桶原理，高度是小的那个，而宽度是两个下标相减。

代码实现：

class Solution 
{
public:
    int maxArea(vector<int>& height) 
    {
        int cur1 = 0, cur2 = height.size() -1;
        int maxV = 0;
        while(cur1 <= cur2)
        {
            int H = min(height[cur1], height[cur2]);
            maxV = max(maxV, (cur2 - cur1) * H);
            // 利用单调性
            if(height[cur1] < height[cur2]) cur1++;
            else cur2--;
        }
        return maxV;
    }
};

算法原理：

首先补充一个数学知识，只要一次判断，得出是否能构成三角形：

若a <= b <= c 且 a +b > c，则可以构成三角形。
所以可以得出一个优化：先把数组排序，O(N*logN)。

数组排完序后：

解法1：暴力枚举，O(N*logN + N^3)，三层for循环，绝对超时。

解法2：利用单调性，使用双指针算法,O(N*logN + N^2)。
(1) 先用c固定最大的元素，定义left 和right分别指向第一个元素，c的下一个元素。
(2) 若nums[left] + nums[right] > nums[c]，由于left和 right之间的数都比 nums[left] 大，与 nums[right] 相加后一定大于c，构成三角形了，就不要一个个枚举了，直接right- -。
(3) 此时三角形个数 = right - left。
(4) 若nums[left] + nums[right] <= nums[c]，由于left和 right之间的数都比 nums[right] 小，与 nums[left] 相加后一定小于c，也不要一个个枚举了，直接left++。
(5) 以上是走完一趟的个数，再c–，固定下一个数。

代码实现：

class Solution 
{
public:
    int triangleNumber(vector<int>& nums) 
    {
    	// 排序
        sort(nums.begin(), nums.end());
        int n = nums.size();
        
        int ret = 0; // 记录个数
        for(int c = n-1; c >= 2; c--)
        {
            int left = 0, right = c - 1;
            while(left < right)
            {
                if(nums[left] + nums[right] > nums[c])
                {
                    ret += right - left;
                    right--;
                } 
                else left++;
            }
        }
        return ret;
    }
};

算法原理：

解法1：暴力枚举，两层for循环，O(N^2)，绝对超时。没有好好利用单调递增这个特性!!

解法2：和上一题的解法2类似，也是利用单调性和双指针算法，O(N)。

细节/技巧问题：

找到数对后就直接 break 结束循环。

代码实现：

class Solution 
{
public:
    vector<int> twoSum(vector<int>& price, int target) 
    {
        vector<int> ret;
        int left = 0, right = price.size() - 1;
        while(left < right)
        {
            int sum = price[left] + price[right];
            if(sum > target) right--;
            else if(sum < target) left++;
            else 
            {
                ret.push_back(price[left]); 
                ret.push_back(price[right]);
                break;
            }
        }
        return ret;
    }
};

算法原理：

解法1：排序+暴力枚举+利用set去重，O(N^3).

解法2：排序+双指针，O(N^2).
这道题其实是上一题的进阶版，首先排序，再固定一个数 a，在该数后面的区间内使用双指针算法快速的找到两个数的和是 -a。

难点/细节/技巧：

这道题的算法不难想，难的是保证不重不漏。

(1) 去重操作有两个方面：一是找到一种结果后，left 和 right 指针要跳过重复元素，二是当使用完一次双指针后，i 也需要跳过重复元素，此时要注意越界。
(2) 还有一个小优化就是当固定的那个数是正数时，后面再也找不到两数和为负数了，直接结束。

代码实现：

class Solution 
{
public:
    vector<vector<int>> threeSum(vector<int>& nums)
    {
        // 排序
        sort(nums.begin(), nums.end());
        vector<vector<int>> vv;
        int n = nums.size();

        for(int i = 0; i <= n-3; i++) // 固定数 a
        {
            if(nums[i] > 0) break; // 小优化
            int left = i +1, right = n-1, a = nums[i];
            // 双指针
            while(left < right)
            {
                int sum = nums[left] + nums[right];
                if(sum > -a) right--;
                else if(sum < -a) left++;
                else 
                {
                    vv.push_back({nums[i], nums[left], nums[right]});
                    // 去重，注意越界
                    while(left < right && nums[left] == nums[left+1]) left++;
                    while(left < right && nums[right] == nums[right-1]) right--;

                    left++;
                    right--;
                }
            }
            while(i < n-1 && nums[i] == nums[i+1]) i++;
        }
        return vv;
    }
};

算法原理：

本道题又是上一题的进阶版。

难点/细节/技巧：

这道题会出现数据溢出的风险。所以当计算两个固定是数之和时，类型定义为 long long。
其余细节参考上一题。

代码实现：

class Solution 
{
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) 
    {
        // 排序
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<vector<int>> vv;
        for(int i = 0; i < n; i++) // 固定数a
        {
            // 三数和
            for(int j = i+1; j < n; j++)// 固定数b
            {
                // 双指针算法
                int left = j+1, right = n-1;
                long long t = (long long)target - (nums[i] + nums[j]);
                while(left < right)
                {
                    long long sum = nums[left] + nums[right];
                    
                    if(sum > t) right--;
                    else if(sum < t) left++;
                    else
                    {
                        vv.push_back({nums[i], nums[j], nums[left], nums[right]});
                        // 去重
                        while(left < right && nums[left] == nums[left+1]) left++;
                        while(left < right && nums[right] == nums[right-1]) right--;
                        left++;
                        right--;
                    }
                }
                while(j < n-1 && nums[j] == nums[j+1]) j++;
            }
            while(i < n-1 && nums[i] == nums[i+1]) i++;
        }
        return vv;
    }
};