【leetcode】双指针算法题

1.算法思想

常见的双指针有两种形式，⼀种是左右指针，⼀种是快慢指针。

1. 左右指针：⼀般用于有序的结构中，也称左右指针。

• 左右指针从两端向中间移动。⼀个指针从最左端开始，另⼀个从最右端开始，然后逐渐往中间逼近。
• 左右指针的终⽌条件⼀般是两个指针相遇或者错开（也可能在循环内部找到结果直接跳出循环），也就是：
  left == right （两个指针指向同⼀个位置）
  left > right (两个指针错开）

2. 快慢指针：⼜称为龟兔赛跑算法，其基本思想就是使⽤两个移动速度不同的指针在数组或链表等序列结构上移动。
   这种方法对于处理环形链表或数组非常有用。
   其实不单单是环形链表或者是数组，如果研究的问题出现循环往复的情况时，均可考虑使用快慢指针的思想。
   快慢指针的实现⽅式有很多种，最常用的⼀种就是：

• 在⼀次循环中，每次让慢的指针向后移动⼀位，而快的指针往后移动两位，实现⼀快⼀慢。

废话不多说，我们来做题。

2.移动零

leetcode 283.移动零

题目要求我们将数组中的0全部移动到数组的末尾，并且其它元素的相对顺序不变，而且不允许开辟额外的数组。
那我们应该如何来解决这一题呢？

算法思路：
在本题中，我们可以⽤⼀个cur 指针来扫描整个数组，另⼀个dest 指针⽤来记录⾮零数序列的最后⼀个位置。
根据cur 在扫描的过程中，遇到的不同情况，分类处理，实现数组的划分。
在cur遍历期间，使[0, dest] 的元素全部都是⾮零元素，[dest + 1, cur - 1] 的元素全是零。

最初，我们不知道非零序列的位置，所以将dest置为-1，cur置为0。cur进行扫描，在扫描过程中：

• 若cur对应元素不为0，cur后移
• 若cur对应元素为0，dest先后移，然后再交换cur与dest，最后cur再后移。

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int dest = -1;
        int cur = 0;
        int n = nums.size();
        while(cur < n)
        {
            //cur不为0，交换
            if(nums[cur] != 0)
            {
                dest++;
                swap(nums[dest],nums[cur]);
            }
            //cur为0,继续后移
            cur++;
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

这样咱们就过啦。

3.复写零

leetcode 1089.复写零

方法一

先统计数组中0的个数，计算复写后数组的大小，使用reserve为数组重新开新的空间，在新空间上直接进行复写，不存在数组越界问题；在复写完成后，再使用对数组进行缩容，使其空间保持原状。

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        int count = 0;
        int n = arr.size();
        int cur = 0;
        while(cur < n)
        {
            if(arr[cur] == 0)
                count++;
            cur++;
        }
        //开辟新空间
        arr.reserve(n+count);
        //此时cur == n,
        cur--;//重新指向最后一个元素
        int dest = n+count-1;
        
        while(cur >= 0)
        {
            if(arr[cur])
            {
                //不是0，无需复写
                arr[dest--] = arr[cur--];
            }
            else
            {
                //复写0
                arr[dest--] = 0;
                arr[dest--] = 0;
                cur--;
            }
        }
        arr.reserve(n);//恢复数组原状
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

简单分析一下复杂度：只遍历了数组，时间复杂度为O(N)；由于使用了reserve开辟了新空间，空间复杂度：O(N)

方法二

能不能在O(1)的空间复杂度下完成该题呢？

我们可以使用两个指针，cur指向最后一个要写的元素，dest指向数组的最后一个位置。

• 若cur为0，复写0，dest移动两次
• 若cur不为0，复写，dest移动一次

那现在的问题就是如何找最后一个要复写的位置。
通过模拟我们可以发现，cur = 0 ,dest = -1；让cur与dest同时走，若cur不为0，则都移动一次；若cur为0，cur移动一次，dest移动两次；直到dest走到数组的末尾，此时cur位置就是最后一个要写的位置

public:
    void duplicateZeros(vector<int>& arr) {
        int cur = 0;
        int dest = -1;
        int n = arr.size();
        while(dest < n-1)
        {
            if(arr[cur] == 0)
                dest += 2;
            else
                dest++;
            cur++;
            }
        }
        for( ; cur >=0; cur--)
        {
            if(arr[cur])
                arr[dest--] = arr[cur];
            else
            {
                arr[dest--] = 0;
                arr[dest--] = 0;
            }
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

此时我们发现程序没过，情况又没想全

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        int cur = 0;
        int dest = -1;
        int n = arr.size();
        while(cur < n)
        {
            if(arr[cur] == 0)
                dest += 2;
            else
                dest++;
            //防止越界
            if(dest >= n-1)
                break;
            cur++;
            
        }
        //已经越界，修正
        if(dest == n)
        {
            arr[n-1] = 0;
            dest-=2;
            cur--;
        }
        //从后向前复写
        for( ; cur >=0; cur--)
        {
            if(arr[cur])
                arr[dest--] = arr[cur];
            else
            {
                arr[dest--] = 0;
                arr[dest--] = 0;
            }
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

此时，该代码地时间复杂度为O(N)；空间复杂度为：O(1)

4.快乐数

leetcode 202.快乐数

根据题意，通过画图我们可以发现，这就是一种循环往复地题目。此时我们就可以考虑双指针算法。

看到这个环形，是不是会想起链表那里有一个判断环形链表的题目，这两题很相似。

我们可以知道，当重复执行x的时候，数据会陷⼊到⼀个「循环」之中。
而「快慢指针」有⼀个特性，就是在⼀个圆圈中，快指针总是会追上慢指针的（证明参考链表部分），也就是说他们总会相遇在⼀个位置上。如果相遇位置的值是1，那么这个数⼀定是快乐数；如果相遇位置不是1的话，那么就不是快乐数。

class Solution {
public:
    int Sum(int n)
    {
        int sum = 0;
        while(n)
        {
            sum += (n%10)*(n%10);
            n/=10;
        }
        return sum;
    }
    bool isHappy(int n) {
        int slow = n;
        int fast = Sum(n);//让fast先走一步
        while(fast != slow)
        {
            slow = Sum(slow);
            fast = Sum(Sum(fast));
        }
        //当二者相等时，若为1，则是快乐数，否则则不是
        return slow == 1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

5.盛水最多的容器

leetcode 11.盛水最多的容器
首先我们要明白，这个容器的容量是：两个柱子之间的距离×两柱中较矮的一个
所以此题我们可以利用双指针，寻找两柱中组成的容器中最大的一个即可。

方法一（暴力求解）

枚举出能构成的所有容器，找出其中容积最大的值。
容器容积的计算⽅式：
设两指针分别指向水槽板的最左端以及最右端，此时容器的宽度为j - i
由于容器的⾼度由两板中的短板决定，因此可得容积公式：v = (j - i) * min( height[i], height[j]）

class Solution {
public:
    int maxArea(vector<int>& height) {
        int v = 0;
        int n = height.size();
        for(int i=0; i<n; i++)
        {
            for(int j = i+1; j<n; j++)
            {
                v = max(v,((j-i)*min(height[i],height[j])));
            }
        }
        return v;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

方法二（左右指针）

观察暴力解法以后，我们可以发现一个规律：
当使用最开始的左右区间算出来一个V1后，我们没必要使用这两个区间中较小的一个去和其它数枚举，因为枚举出来的结果一定是小于V1的。

所以，可以按照以下步骤：

• 先根据当前两柱计算V
• 舍去两柱子中较小的一个
• 根据新的柱子再计算体积tmp，V = max(V,tmp)

class Solution {
public:
    int maxArea(vector<int>& height) {
        int v = 0;
        int left = 0;
        int right = height.size()-1;
        while(left < right)
        {
            //先计算当前两柱组成的大小
            int tmp = (right-left) * min(height[left],height[right]);
            v = max(v,tmp);
            if(height[left] < height[right])
                left++;
            else
                right--;
        }
        return v;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

6.有效三角形的个数

leetcode 611.有效三角形的个数

我们都知道，组成三角形的条件是：任意两边之和大于第三边。

方法一（暴力求解）

但是使用这个条件只想到一个暴力解法，虽然说是暴⼒求解，但是还是想优化⼀下
判断三⻆形的优化：

• 如果能构成三⻆形，需要满⾜任意两边之和要大于第三边。但是实际上只需让较小的两条边之和大于第三边即可。
• 因此我们可以先将原数组排序，然后从小到大枚举三元组，一方面省去枚举的数量，另一方面方便判断是否能构成三⻆形。

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(),nums.end());
        int count = 0;
        for(int i=0; i<n; i++)
        {
            for(int j=i+1; j<n; j++)
            {
                for(int k = j+1; k<n; k++)
                {
                    if(nums[i] + nums[j] > nums[k])
                        count++;
                }
            }
        }
        return count;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

方法二（左右指针）

将数组排序以后我们可以发现，如果我们固定最右侧数为第三条边，就只需使用左右指针找另外两条即可。
而且如果最左侧的数和右侧数加起来已经大于第三边了，那么左侧和右侧之间的数一定大于第三边，无需再枚举。

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        //先按照升序排序
        sort(nums.begin(),nums.end());
        int max = nums.size() - 1;
        int ret = 0;

        //至少要存在3条边
        while(max >= 2)
        {
            int left = 0;
            int right = max - 1;

            while(left < right)
            {
                if(nums[left] + nums[right] > nums[max])
                {
                    ret += right - left;
                    right--;
                }
                else
                    left++;
            }
            max--;
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

7.两数之和

leetcode 179.和为target的两个数

由于该数组是升序的，那么我们可以直接使用双指针，计算左右指针之和

• 若和小于target，左指针右移
• 若和大于target，右指针左移

class Solution {
public:
    vector<int> twoSum(vector<int>& price, int target) {
        vector<int> ret;
        int left = 0;
        int right = price.size()-1;
        while(left < right)
        {
            if(price[left]+price[right] < target)
                left++;
            else if(price[left] + price[right] > target)
                right--;
            else
            {
                break;
            }
        }
        return {price[left],price[right]};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

8.三数之和

leetcode 15.三数之和

这一题和上一题两数之和的解法非常类似，唯一的不同点就是：该题不允许有重复的三元组。

• 先排序
• 固定一个数aim
• 使用两数之和法，找和为 - aim 的两个数即可
  • 不漏
    • 找到一个数以后，left++,right- -继续找
  • 去重
    • left 与right均需要去重，如果left++后任然和之前的相同，那就继续++；right同理，仍需要 - -
    • aim去重，如果aim移动后，仍然和上一个相等，那就继续移动

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ret;
        sort(nums.begin(),nums.end());
        int n = nums.size();
        int i = 0;
        while(i < n)
        {
            if(nums[i] > 0)//若num对应的都已经大于0，那么left 与right就更大，和不可能为0了
                break;
            int aim = -nums[i];//固定一个数，取其相反数
            int left = i+1;
            int right = n-1;
            while(left < right)
            {
                int sum = nums[left] + nums[right];
                if(sum > aim)
                    right--;
                else if(sum < aim)
                    left++;
                else
                {
                    ret.push_back({nums[i],nums[left],nums[right]});
                    //避免遗漏，继续找
                    left++;
                    right--;
                    //left,right去重
                    while(left < right && nums[left] == nums[left-1])
                        left++;
                    while(left < right && nums[right] == nums[right+1])
                        right--;
                }
            }
            i++;
            while(i < n && nums[i] == nums[i-1])
                i++;
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

9.四数之和

leetcode 18.四数之和
该题是在三数之和的基础之上的变形。

仍然还是采用上面的做法，

• 先排序
• 固定一个数a
• 利用三数之和，固定一个数b,找和为target - nums[a] - nums[b]的数
  • 不漏
    • 找到一个数以后，left++，right- -继续找
  • 去重
    • left 与right均需要去重，如果left++后任然和之前的相同，那就继续++；right同理，仍需要 - -
    • b去重，如果b移动后，仍然和上一个相等，那就继续移动
    • a去重，如果a移动后，仍然和上一个相等，那就继续移动

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(),nums.end());
        vector<vector<int>> ret;
        int n = nums.size();
        int a = 0;
        while(a < n)
        {
            int b = a+1;
            while(b < n)
            {
                long long aim = (long long)target -nums[a] - nums[b];
                int left = b+1;
                int right = n-1;
                while(left < right)
                {
                    if(nums[left] + nums[right] < aim)
                        left++;
                    else if(nums[left] + nums[right] > aim)
                        right--;
                    else
                    {
                        ret.push_back({nums[a],nums[b],nums[left],nums[right]});
                        left++;
                        right--;
                        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 ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43