双指针算法——部分OJ题详解

关于双指针算法：

1，对撞指针

2，快慢指针

部分OJ题详解

283.移动零

1089.复写零

202.快乐数

11.盛水最多的容器

611.有效三角形的个数

剑指offer 57.和为s的两个数字

15.三数之和

18.四数之和

关于双指针算法：

双指针算法是一种经典算法，一般有两种：对撞指针和快慢指针。

1，对撞指针

一般用于顺序结构中，也叫做左右指针。意思是从定长顺序结构的最左端和最右端向中间移动，当在循环内部找到结果或者满足：left == right 和 left > right时就退出循环

2，快慢指针

和如名字一样，两个指针在顺序结构的同一端同时移动，一个指针一次往后移动一次，一个一次移动两次。该算法非常适合用于处理数组和环形数据结构问题。

部分OJ题详解

283.移动零

283. 移动零 - 力扣（LeetCode）

该题目可归类为“数组划分，数组分块”问题，可以使用快慢指针将整个数组分成0区间和非0区间。

定义两个指针：cur和dest。其中cur的作用很简单，就是从左往右遍历数组，dest的作用则是划分0区间和非0区间，表示已经划分好的0区间的最后一个如下图：

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

1089.复写零

1089. 复写零 - 力扣（LeetCode）

该题目简单解释就是：给一个数组arr，将每一个出现的0往后复写一位，不覆盖后面的数据，其余元素往后移动，不要越界，只能修改原数组。

咱们来分析这道题：

首先我们要找到最后一个要复写的数的位置下标，定义双指针cur=0，dest=-1，cur先开始遍历，如果cur不为0，dest和cur都走一步，如果cur为0，dest走两步，最后当dest走到数组结尾时，开始复写0
有个特例，[1, 0, 2, 3, 0 ,4]，该数组按照上面的步骤，最后的cur会指向第二个0，dest最后走到了第7个位置也就是数组后面一个位置，但是由于cur为0，所以在复写的时候会把dest改为0，造成越界访问，所以需要处理下越界情况
当最后dest == arr.size()时，arr[n - 1] = 0; dest += 2;

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

            if(dest >= n - 1) break;
            //当dest合法时，在cur++
            cur++;
        }
        //2，处理边界情况
        if(dest == n)
        {
            arr[n - 1] = 0;
            cur--;
            dest += 2;
        }
        //3，开始从后往前复写0
        while(cur >= 0)
        {
            if(arr[cur] != 0)
            {
                arr[dest--] = arr[cur--]; 
            }
            else
            {
                arr[dest--] = 0;
                arr[dest--] = 0; //复写0
                cur--;
            }
        }
    }
};

202.快乐数

202. 快乐数 - 力扣（LeetCode）

题目有点复杂，但是相信大家看来示例之后很快能理解，下面我们来分析下这个题目：

这道题一共有三种情况，第一种情况是：和示例一样，输入19，最后会变成1，变成1之后会陷入无限循环 第二种情况是：输入2，无限循环，但始终变不到1 第三种情况就是始终变不到1并且无重复数字，但该题不考虑
以第一第二种情况为例，最后都会变成一个数并且无限循环，也就是说两种情况带入链表的话最后会有一个“环”，所以这道题和我们的“判断链表是否有环”很相似，这道题我们只需要判断环种的数是否为1即可
所以我们采用快慢指针来解，然后因为环的特性，只要判断两个指针相遇时的值即可
最后，我们可以直接用数来代替指针的租用，假设slow指针=2，那么平方之后变成了4，就相当于在数组中对指针进行了++，这是慢指针，所以快指针进行两次平方，也就是++两次

class Solution {
public:
    int bitSum(int n) //返回n数每一位上的平方和
    {
        int sum = 0;
        while(n > 0)
        {
            int t = n % 10;
            sum += t*t;
            n /= 10;
        }
        return sum;
    }
    bool isHappy(int n) 
    {
        int slow = n, fast = n;
        fast = bitSum(fast);
        while(fast != slow)
        {
            slow = bitSum(slow);
            fast = bitSum(fast);
            fast = bitSum(fast);
        }
        return slow == 1;
    }
};

11.盛水最多的容器

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

解释一下题目：给一个长度为n的整数数组height，每个元素代表一个垂线表示容器的高度，找出其中两条线，使得它们与x轴共同构成的容器可以容纳最多的水，返回容器可以存储的最大水量。下面我们来分析下这道题：

首先是暴力解法：用两个for循环将所有的可容纳的水的容量全部枚举出来，列成数组然后排序，选出最大值。这种解法肯定会超时，因为时间复杂度为O(N*2)
我们先选一个区间：[6, 2, 5, 4]，首先计算6到4的容量，为6 * 3 = 18，当向内枚举时，也就是2和4，5和4，容器的宽度是一直在减小的，但是高度会有两种情况：当向内枚举是碰见了一个小的数（2比4小），所以高度减小；当碰到了一个大的数（5比4大），虽然高度不变，但是宽度减小了，所以总体容量还是在减小。那么我们就可以去掉2和4，5和4的枚举，就能减少枚举次数
然后就是总体了[1, 8, 6, 2, 5, 4, 8, 3, 7]。先算1和7，得出v1，1比7小，所以左指针++；计算8到7，得出v2，8比7大，所以右指针--；再算8到3，得出v3，8比3大，所以右指针++
像这样利用单调性和双指针来搞，只需要遍历一遍数组就可以了，就可以把暴力解法的O(N * 2)变成了O(N)

class Solution {
public:
    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(ret, v);
            //计算完毕，移动指针，谁小移动谁
            if(height[left] < height[right])
            {
                left++;
            }
            else
            {
                right--;
            }
        }
        return ret;
    }
};

611.有效三角形的个数

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

解释下这道题：给我们一个数组，选择数组中任意三个数尝试组成一个三角形，返回能够组成三角形的个数，下面我们来分析下这道题：

首先是暴力解法，既然要找三个数，那就用三个循环穷举所有情况，然后只需判断a+b是否大于c即可，但是我们可以先对数组排序，这样原本要三个数各判断一次，排序后只需判断一次
排完序后再进行列举，只有两种情况：①a+b>c ②a+b <= c，我们只需对这两个情况做判断即可
假设要处理的数组为[2, 2, 3, 4, 5, 9, 10]，我们可以先固定最大值10，然后定义双指针，left指向2，right指向9；2+9>10 符合情况①，这时候可以看到2后面的值都比2大，那么2后面的数和9相加肯定是大于10的，所以就不要再left++了，直接将后面的情况全部纳入，也就是可形成的三角形数直接+(right-left)，就可以省去很多次计算和比较
那么left不要动，那么自然是right往左移了，right接着指向5，这时候2+5<10，符合情况②，那么right就不要再往左走了，因为5左边的数肯定比5小，不可能组成三角形，所以要left++再判断
然后按照上面的步骤把固定10的情况全搞定，然后再固定9，这样依次判断，就能用一个循环解决问题

class Solution {
public:
    int triangleNumber(vector<int>& nums) 
    {
        //1，排序优化
        sort(nums.begin(), nums.end());

        //2，采用双指针解决问题
        int ret = 0;//统计最终个数
        int n = nums.size();
        for(int i = n-1; i >= 2; i--)
        {
            //利用双指针快速统计符合要求的三元组个数
            int left = 0, right = i - 1;
            while(left < right)
            {
                //判断能否构成三角形
                if(nums[left] + nums[right] > nums[i]) //符合情况①
                {
                    ret += right - left;
                    right--;
                }
                else //符合情况②
                {
                    left++;
                }
            }
        }
        return ret;
    }
};

剑指offer 57.和为s的两个数字

LCR 179. 查找总价格为目标值的两个商品 - 力扣（LeetCode）

解释下这道题：给一个升序的数组和一个数字s，在数组里找两个数使和等于s，如果有多种结果返回一组即可，下面我们来分析下这道题：

首先还是暴力解法：两个for循环穷举全部情况，一个一个相加判断即可，但是暴力解法没有用到数组已经有序这个条件，所以这道题我们还是用单调性和双指针来解决。
假设给的数组是[2, 7, 11, 15, 19, 21]，s=30；所以当相加的时候会有三种情况①sum>t ②sum<t ③sum=t。
首先定义left指针指向2，right指针指向21，2+21<30，符合情况②，所以21前面的数都小于21，所以直接全部排除，right不动，left++到7的时候仍然小于20，left再++
当left指向11时，11+19==30，符合要求于是返回，如果再次符合情况②，left再++，如果符合情况①，那么right--
就这样我们只需要遍历一次数组就能找到等于30的两个数了

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

15.三数之和

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

解释一下题目：给你一个数组，在这个数组中随便选三个数使它们的和为0，并且三个数互不相同，返回所有相加为0的三个数组合，顺序没有要求但是元素的下标不能一样，假设输入：[-1, 0, 1, 2, -1, -4] ，我们可以选出三个[-1, 0, 1] [-1, 2, -1] [0, 1, -1]但是只返回前两个，是因为第三个和第一个顺序不一样，但是元素一样的，这样的情况我们二选一返回。下面我们来分析下这道题：

首先是暴力解法，三个for暴力穷举，然后将每个选出来的三个数组成vector，然后排序+去重，去重可以用set容器去重，但是暴力解法时间复杂度为O(N^3)
其实这道题和上面的“和为s的两个数”的题目很像，只是s变成了0，两数之和变为了三数之和，所以我们也可以尝试用排序+双指针来解决
首先对原数组进行排序，假设排完序后是[-4, -4, -1, 0, 0, 0, 1, 1, 4, 4, 5, 6]，可以先固定第一个-4，i=-4，然后定义双指针left指向第二个-4，right指向6，然后可以和“有效三角形个数”题目一样，找到left和right的和等于 -(-4)即可，然后再次固定-1，重复操作即可
但是这道题有一些细节需要额外处理：①不借助set去重，原数组排序后已经有序，所以找到一种结果之后，left和right都要跳过重复元素，并且使用完一个固定数i之后，i也要跳过重复元素，并且，跳过重复元素的时候也要注意越界问题，比如[0, 0, 0, 0]
②找到一种结果之后，指针不要停，要继续往里缩继续找

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

        //2，利用双指针解决问题
        int n = nums.size();
        for(int i = 0; i < n;) //固定数a
        {
            if(nums[i] > 0) break; //优化：如果最小的数已经大于0，那么后面的数相加一定不等于0
            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]});
                    left++;
                    right--; //不漏
                    while(left < right && nums[left] == nums[left - 1]) left++; //跳过重复元素
                    while(left < right && nums[right] == nums[right + 1] ) right--; //对指针去重
                }
            }
            //对i去重
            i++;
            while(i < n && nums[i] == nums[i - 1]) i++;
        }
        return vv;
    }
};

18.四数之和

18. 四数之和 - 力扣（LeetCode）

解释下题目：和三数之和题目一样，只是变成了4个数的和为0，下面来分析下这道题：

暴力解法就是还是4次循环 + set去重，但是时间复杂度为O(N^4)，巨耗时间
其实我们可以复用我们三数之和的算法，固定一个数，然后在这个数后面使用三数之和算法，然后再把固定的数往后面挪，再使用三数之和，依次循环就可以解决四数之和的问题

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) 
    {
         vector<vector<int>> vv;
        //1，排序
        sort(nums.begin(), nums.end());

        //2，利用双指针解决问题
        int n = nums.size();
        for(int a = 0; a < n;) //固定数a
        {
            //利用三数之和解决问题
            for(int b = a + 1; b < n;)
            {
                //双指针
                int left = b + 1, right = n -1;
                long long aim = (long long)target - nums[a] - nums[b]; //利用双指针找到两个数的和等于aim即可
                while(left < right)
                {
                    int sum = nums[left] + nums[right];
                    if(sum < aim) 
                        left++;
                    else if(sum > aim)
                        right--;
                    else
                    {
                        vv.push_back({nums[a], nums[b], nums[left++], nums[right--]}); //找到一种结果
                        //去重操作 --> ①先去重left和right，②再去重b，③最后再a去重
                        //去重①
                        while(left < right && nums[left] == nums[left-1]) left++;
                        while(left < right && nums[right] == nums[right+1]) right--;
                    }
                }
                //去重②
                b++;
                while(b < n && nums[b] == nums[b-1]) b++;
            }
            a++;
            while(a < n && nums[a] == nums[a-1]) a++;
        }
        return vv;
    }
};