双指针算法（一）

目录

移动零

复写零

快乐数

盛水最多的容器

双指针与单调性结合

有效三角形的个数

查找总价格为目标值的两个商品

两数之和?Ⅱ - 输入有序数组?

---

双指针算法是通过定义两个指针不断单向移动来解决问题的一种算法。但双指针算法，是一个抽象的思想概念，可以用来解决数组划分、数组分块等问题。

它通常并不是真的定义两个指针，例如在 vector、string 中就经常通过下标来充当指针。

移动零

力扣链接：移动零

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

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

题目的意思：很明确，将所有非零元素移至数组最前面，数组中的零都放在数组偏后面的位置。

思路：定义两个 ‘指针’?cur 和 dest ，cur指针用来从左往右扫描遍历数组，一直指向扫描过的最后一个元素，dest指针一直指向遍历过的数组范围内最后一个不为零的位置。

具体做法：定义cur为0，dest为 -1（因为不知道第一个位置是否需要被交换），cur指针从左往右扫描数组，遇到等于0的元素直接跳过，遇到不等于零的元素，先让 dest 指针的位置加1，然后交换 cur 和 dest 两个位置的值后，两个指针再分别后移一位......如此循环直到最后cur扫描至数组最后一位。

此时数组就被划分为两个部分，因为dest指向的是遍历过的数组范围内最后一个不为零的位置，而扫描已经结束，所以 dest 指针指向的是最后一个不为 0 的位置，cur指针指向的是数组最后一个位置，两个指针中间的数就全是移动后的零。

代码详解（核心代码模式）

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

复写零

力扣链接：复写零

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

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

思路：先根据 ‘异地’ 操作将数组进行按规则复写，然后优化为双指针下的 ‘就地’ 操作。

异地操作方法：两个指针 cur 和 dest 分别指向两个数组，一个原数组，一个与原数组空间相同的新数组。利用 cur 指针对原数组进行遍历，遇到非零元素，在新数组中按序拷贝，遇见0元素，就在新数组中连续拷贝两次。?

原地操作优化思路：先使用 ‘异地’ 操作的思想，找到最终两个指针复写结果的位置，从前往后完成复写！

具体做法：

（1）定义 cur 为0，dest 为 -1。cur 指针遍历数组，遇到不为0的数，dest向前移动一位，遇到0，dest 向前移动两位，当 dest 到达数组最后一个位置的时候，cur和dest的位置就是从后往前开始复写的位置。

（2）cur 指针开始向前走，遇到非零，dest就将这个数拷贝过去，dest前移一位；遇到0，dest就拷贝两个零，同时向前移动两位.....当cur移动到数组最开始的位置的时候，复写就结束了！

代码详解（核心代码模式）

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        int cur = 0, dest = -1;
        int n = arr.size();
        //第一步：找到复写的位置
        while (dest <n)
        {
            if (arr[cur] != 0)
                dest++;
            else if (arr[cur] == 0)
                dest += 2;
            if (dest >=n - 1)
                break;
            cur++;
        }
        //处理特殊情况
        if (dest==n)//dest指针越界，说明原数组倒数第二个位置为0
        {
            cur--;
            arr[n - 1] = 0;
            dest -= 2;
        }
        while (cur >= 0)
        {
            if (arr[cur] != 0)
            {
                arr[dest--] = arr[cur];
            }
            else if (arr[cur] == 0)
            {
                arr[dest--] = arr[cur];
                arr[dest--] = arr[cur];
            }
            cur--;
        }
    }
};

注意点：当原数组的倒数第二个位置为0的时候，需要在循环结束后单独处理一下，否则就会造成数组越界！?

快乐数

力扣链接：快乐数

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

「快乐数」?定义为：

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

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

思路：快乐数定义的第二点非常重要，‘重复这个过程直到这个数字变为 1 ，也可能是 无限循环 但始终变不到1’。那么这个问题中，运算每进行一步，都可以看做链表往前走一步，其实可以抽象成链表成环问题，再使用 ‘快慢指针’ 来解决。

这里的快指针就是计算每位平方和后再将结果计算平方和，慢指针就只计算一次平方和......一直进行这样的操作，既然这个数字最后都会‘循环’，那么就是变成1循环还是其他多个数进行循环的问题了。

当快指针和慢指针相遇（相等）的时候，判断这个数是不是1，如果是1，这个数 n 就是快乐数，反之则不是。

代码详解（核心代码模式）

class Solution {
public:
    int Sumbit(int n)
    {
        int sum = 0;
        while(n)
        {
            int x = n % 10;
            sum += x*x;
            n /= 10;
        }
        return sum;
    }
    bool isHappy(int n) {
        //快慢指针
        int fast = n,slow = n;
        do
        {
            slow = Sumbit(slow);
            fast = Sumbit(Sumbit(fast));    
        }while(fast != slow);
        if(fast == 1)
            return true;
        else
            return false;
    }
};

快指针和慢指针刚开始都等于这个数字 n，定义一个计算各位平方和的函数：慢指针调用1次，快指针调两次。然后使用 do...while 循环找到下次 快慢指针相等的值，判断这个值是否等于1即可。

盛水最多的容器

力扣链接：盛水最多的容器

给定一个长度为?n?的整数数组?height?。有?n?条垂线，第?i?条线的两个端点是?(i, 0)?和?(i, height[i])?。

找出其中的两条线，使得它们与?x?轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

思路：容器能盛水的最大高度是由两侧最低的柱子决定的！先计算出两侧开始的水的容量，设置为Max。利用双指针从两边到中间，高度较低一边的指针向中间移动，并重新计算容量，如果新容量大于初始的Max，就更新Max的值。两个指针相遇的时候，Max的值就是容器能容纳水的最大值。

代码详解（核心代码模式）

class Solution {
public:
    int V(vector<int>& height , int x , int y)
    {
        return min(height[x],height[y]) * (y-x);
    }
    int maxArea(vector<int>& height) {
        int left = 0, right = height.size()-1;
        int Max = 0;
        while(left != right)
        {
            int v = V(height,left,right);
            Max = max(v,Max);
            if(height[left] < height[right])
            {
                left++;
            }   
            else
                right--;
        }
        return Max;
    }
};

双指针与单调性结合

有效三角形的个数

力扣链接：有效三角形的个数

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

前提：一组数中，两个较小的数相加大于较大的数，就能组成三角形（任意三边之和大于第三边的一组数能构成三角形的推论）

思路：先排序，保证不降序排列。从数组右侧开始固定最大的数，利用双指针（一个指针在最左边，另一个指针在固定数的左边），来确定固定的这个数的左半区间中能构成三角形的个数，然后向左更新这个被固定的数，重复上面的步骤，直至左半区间只有两个数为止循环结束。

确定左半区间中能构成三角形的个数：设固定的数位置为 tmp，则right的位置为 tmp -1 ，left 位置的值为 0。判断两个位置数相加后的结果与固定数的大小：如果大于，说明两个指针 [ left 、right ) 之间的所有数，都能与 right、tmp形成三角形，则能形成三角形的个数将会增加?( right - left )个；如果小于等于，说明 left 这边的值不够大，将 left 指针再加1，重复上面的比较过程。当left指针和right指针相遇，或者两者的数大于 tmp 位置的数时结束本轮循环，更新固定数的位置继续上述过程。

代码详解（核心代码模式）

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        //只要两个小数相加大于大数，就能构成三角形
        sort(nums.begin(),nums.end());//先排序
        size_t sum = 0;
        //外层循环，固定一个最大的数
        for(int tmp = nums.size()-1; tmp >= 2; tmp --)
        {
            int right = tmp-1;
            int left = 0;
            //利用双指针算法
            while(right != left)
            {
                if(nums[left] + nums[right] > nums[tmp])
                {
                    sum += (right-left);
                    right--;
                }
                else
                {
                    left++;
                }
            }
        }
        return sum;
    }
};

查找总价格为目标值的两个商品

两数之和?Ⅱ - 输入有序数组?

这两个题是一种思路，一个返回数。一个返回下边。但都是双指针思路、利用单调性来做题！

设定两个指针，一个在左边，一个在右边，因为数组是有序的，所以左边是最小的，右边是最大的，两个指针往中间移动，根据和与目标数值的大小关系，来确定指针的移动，最后两个指针停留于的位置，就是两个数的和等于目标值的位置。?

查找总价格为目标值的两个商品代码详解（核心代码模式）

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

两数之和?Ⅱ - 输入有序数组（核心代码模式）?

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