LeetCode双指针经典题目解析

283. 移动零

解题思路

  • 使用双指针技巧
  • 左指针标记当前需要填充非零数的位置
  • 右指针遍历数组寻找非零数
  • 遇到非零数就交换两个指针位置的值

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int start = 0;
        int size = nums.size();
        for(int i = 0; i < size ; i++)
        {
            if(nums[i] != 0)
            {
                swap(nums[start++],nums[i]);
            }
        }
    }
};

11. 盛最多水的容器

解题思路

  • 使用左右双指针向中间收缩
  • 每次移动较短的那个边
  • 计算过程中维护最大面积
  • 面积计算：宽度（右指针-左指针）* 高度（两指针高度的较小值）

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0; 
        int right = height.size()-1;
        int maxA = 0;
        while(left < right)
        {
            int minheight = min(height[left],height[right]);
            int vol = minheight * (right - left);

            maxA = max(maxA,vol);

            if(height[right]<height[left])
            {
                right--;
            }
            else left++;
        }
        return maxA;
    }
};


15. 三数之和

解题思路

  • 先将数组排序
  • 固定第一个数，然后用双指针寻找另外两个数
  • 注意去重处理：
    1. 固定数字时跳过重复值
    2. 左右指针移动时也要跳过重复值
  • 优化：
    1. 当固定数字大于0时可以直接break
    2. 当和大于0时右指针左移，小于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
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int size = nums.size();
        vector<vector<int>> ret;
        for(int i = 0; i< size; i++)
        {   
            if(i!=0&&nums[i]==nums[i-1]) continue;
            int target = 0 - nums[i];

            int left = i+1;
            int right = size -1;

            while(left < right)
            {
                if(nums[left]+nums[right]<target)
                {
                    left++;
                }
                else if(nums[left]+nums[right]>target)
                {
                    right--;
                }
                else 
                {
                    ret.push_back({nums[i],nums[left],nums[right]});
                    int pre = nums[left];
                    while(left<right && pre == nums[left])left++;
                }
            }
        }
        return ret;
    }
};


42. 接雨水

解题思路

  • 双指针法：
    1. 使用左右指针从两端向中间移动
    2. 维护左右两边的最大高度
    3. 较低的一边可以确定当前位置能接的雨水
    4. 移动较低的一边的指针

代码实现

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
class Solution {
public:
    int trap(vector<int>& h) {
        //记录每一根柱子左右的最大值中的最小值,若没有同时有比他自身大的最大值则设置为0
        int ret=0;
        int m=0;//除柱子本身前缀最大值
        int n=h.size();
        vector<int>a(n,0);


        for(int i=0;i<n;i++){
            if(m>h[i])
            a[i]=m;
            else a[i]=0;
            m=max(m,h[i]);
        }

        m=0;

        for(int i=n-1;i>=0;i--){
            if(m>h[i])
            a[i]=min(m,a[i]);
            else a[i]=0;
            m=max(m,h[i]);
        }
        
        for(int i=0;i<n;i++){
            if(a[i])
            ret+=a[i]-h[i];
        }
        return ret;


    }
};