LeetCode Hot 100 (2) 双指针

小帅 1/2/2024 LeetCode

# 283.移动零 (opens new window)

题目：

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

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

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

1
2

示例 2:

输入: nums = [0]
输出: [0]

1
2

提示:

1 <= nums.length <= 10^4
-2^31 <= nums[i] <= 2^31 - 1

进阶：你能尽量减少完成的操作次数吗？

思路：

用快慢指针，快指针遍历每个数，慢指针对应的位置存非零的数，之后补0

代码：

C++代码

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int slowIndex = 0;
        for(int fastIndex=0;fastIndex<nums.size();fastIndex++) {
            if(nums[fastIndex]!=0) nums[slowIndex++] = nums[fastIndex];
        }
        for(int i=slowIndex;i<nums.size();i++) nums[i] = 0;
    }
};

1
2
3
4
5
6
7
8
9
10

Go代码

func moveZeroes(nums []int)  {
    slowIndex := 0
    for fastIndex:=0;fastIndex<len(nums);fastIndex++ {
        if nums[fastIndex]!=0 {
            nums[slowIndex] = nums[fastIndex]
            slowIndex++
        }
    }
    for i:=slowIndex;i<len(nums);i++ {
        nums[i] = 0
    }
}

1
2
3
4
5
6
7
8
9
10
11
12

# 11.盛最多水的容器 (opens new window)

题目：

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

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

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

说明：你不能倾斜容器。

示例 1：

输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

1
2
3

示例 2：

输入：height = [1,1]
输出：1

1
2

提示：

n == height.length
2 <= n <= 10^5
0 <= height[i] <= 10^4

思路：

左右两侧定义指针，用贪心的方式，每次移动高度相对较小的那一侧

代码：

C++代码

class Solution {
public:
    int maxArea(vector<int>& height) {
        int res = 0;
        int i = 0, j = height.size()-1;
        while(i<j) {
            int temp = min(height[i], height[j])*(j-i);
            res = max(res, temp);
            if(height[i]<height[j]) i++;
            else j--;
        }
        return res;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14

Go代码

func maxArea(height []int) int {
    res := 0
    i, j := 0, len(height)-1
    for i<j {
        temp := min(height[i],height[j])*(j-i)
        res = max(res, temp)
        if height[i] < height[j] {
            i++
        } else {
            j--
        }
    }
    return res
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 15.三数之和 (opens new window)

题目：

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

1
2
3
4
5
6
7
8

示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

1
2
3

示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

1
2
3

提示：

3 <= nums.length <= 3000
-10^5 <= nums[i] <= 10^5

思路：

先排序，然后针对每个数对其右侧的数找两数之和符合要求的数，找两数之和符合要求的数可以定义左右指针进行遍历，要注意针对可能重复的情况进行处理，这样的话时间复杂度就是O(n^2)。

代码：

C++代码

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        vector<vector<int>> res;
        for(int i=0;i<nums.size();i++) {
            if(i>0&&nums[i]==nums[i-1]) continue;
            int j = i+1, k = nums.size()-1;
            while(j<k) {
                if(nums[i]+nums[j]+nums[k]>0) k--;
                else if(nums[i]+nums[j]+nums[k]<0) j++;
                else {
                    res.push_back({nums[i],nums[j],nums[k]});
                    while(j<k&&nums[j]==nums[j+1]) j++;
                    while(j<k&&nums[k]==nums[k-1]) k--;
                    j++;
                    k--;
                }
            }
        }
        return res;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

Go代码

func threeSum(nums []int) [][]int {
    res := make([][]int,0)
    slices.Sort(nums)
    for i:=0;i<len(nums);i++ {
        if i>0&&nums[i]==nums[i-1] {
            continue
        }
        j, k := i+1, len(nums)-1
        for j<k {
            if nums[i]+nums[j]+nums[k]>0 {
                k--
            } else if nums[i]+nums[j]+nums[k]<0 {
                j++
            } else {
                res = append(res,[]int{nums[i],nums[j],nums[k]})
                for j<k&&(nums[j]==nums[j+1]) {
                    j++
                }
                for j<k&&(nums[k]==nums[k-1]) {
                    k--
                }
                j++
                k-- 
            }
        }
    }
    return res
}

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

# 42.接雨水 (opens new window)

题目：

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

1
2
3

示例 2：

输入：height = [4,2,0,3,2,5]
输出：9

1
2

提示：

n == height.length
1 <= n <= 2 * 10^4
0 <= height[i] <= 10^5

思路：

定义两个单调栈分别用来获取每个位置左右两侧最大的高度，然后遍历一遍数组，根据左右两侧最大高度的最小值即可得到这个位置存水量，相加每个位置存水量即可得到答案。

代码：

C++代码

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        vector<int> left_max(n);
        //构建一个单调递减的单调栈,用数组模拟单调栈，找每个元素左边最大的元素的位置
        vector<int> stk1(n);
        int st = -1;
        for(int i=0;i<n;i++) {
            if(st==-1) {
                left_max[i]=-1;
                stk1[++st] = i;
                continue;
            }
            while(st>=0&&height[i]>=height[stk1[st]]) st--;
            if(st==-1) {
                left_max[i]=-1;
            } else {
                left_max[i] = stk1[0];
            }
            stk1[++st] = i;
        }

        vector<int> right_max(n);
        //构建一个单调递减的单调栈,用数组模拟单调栈，找每个元素右边最大的元素的位置
        vector<int> stk2(n);
        st = -1;
        for(int i=n-1;i>=0;i--) {
            if(st==-1) {
                right_max[i]=-1;
                stk2[++st] = i;
                continue;
            }
            while(st>=0&&height[i]>=height[stk2[st]]) st--;
            if(st==-1) {
                right_max[i]=-1;
            } else {
                right_max[i] = stk2[0];
            }
            stk2[++st] = i;
        }
        int res = 0;
        for(int i=0;i<n;i++) {
            if(left_max[i]==-1||right_max[i]==-1) continue;
            else {
                int temp = min(height[left_max[i]],height[right_max[i]]);
                res += temp - height[i];
            }
        }
        return res;
    }   
};

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
44
45
46
47
48
49
50
51
52

Go代码

func trap(height []int) int {
    n := len(height)
    left_max := make([]int, n)
    stk1 := make([]int,n)
    st := -1
    for i:=0;i<n;i++ {
        if st==-1 {
            left_max[i] = -1
            st++
            stk1[st] = i
            continue
        } 
        for st>=0&&height[stk1[st]]<=height[i] {
            st--
        }
        if st==-1 {
            left_max[i] = -1
        } else {
            left_max[i] = stk1[0]
        }
        st++
        stk1[st] = i
    }

    right_max := make([]int, n)
    stk2 := make([]int,n)
    st = -1
    for i:=n-1;i>=0;i-- {
        if st==-1 {
            right_max[i] = -1
            st++
            stk2[st] = i
            continue
        } 
        for st>=0&&height[stk2[st]]<=height[i] {
            st--
        }
        if st==-1 {
            right_max[i] = -1
        } else {
            right_max[i] = stk2[0]
        }
        st++
        stk2[st] = i
    }

    res := 0
    for i:=0;i<n;i++ {
        if left_max[i]==-1||right_max[i]==-1 {
            continue
        }
        temp := min(height[left_max[i]],height[right_max[i]])
        res += temp-height[i]
    }
    return res
}

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
44
45
46
47
48
49
50
51
52
53
54
55
56

小帅的博客

Choose mode