抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

LeetCode-Hot100-双指针

leetcode

发布于：2024年9月30日

字数：2.6k 字

时长：11 分钟

前言

题单LeetCode 热题 100的双指针部分，给出解析。

283. Move Zeroes

原题链接

题目描述

Given an integer array nums, move all 0‘s to the end of it while maintaining the relative order of the non-zero elements.

Note that you must do this in-place without making a copy of the array.

Constraints:

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

Follow up: Could you minimize the total number of operations done?

解题方法

本题目要求将整数数组 nums 中的所有 0 移动到数组末尾，并且保持非零元素的相对顺序的问题，考虑实现一个原地算法，定义两个指针：

  • left：跟踪下一个非零元素应该放置的位置。
  • right：遍历数组。

算法步骤：

  • 初始化 left 为 0。这个指针将用于将非零元素放置在正确的位置。
  • 使用 right 从 0 遍历到数组的末尾。
  • 当 right 指向的元素不是 0 时，将该元素放到 left 位置，然后将 left 加 1。
  • 当所有非零元素都被放置在正确位置后，将数组中 left 到数组末尾的部分填充为 0。

代码实现

Python版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        left = 0
    
        for right in range(len(nums)):
            if nums[right] != 0:
                nums[left] = nums[right]
                left += 1
        
        for i in range(left, len(nums)):
            nums[i] = 0

Java版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public void moveZeroes(int[] nums) {
        int left = 0;
        for(int right = 0; right < nums.length; right++)
        {
            if (nums[right] != 0) {
                nums[left++] = nums[right];
            }
        }
        while (left < nums.length) {
            nums[left++] = 0;
        }
    }
}

复杂度分析

时间复杂度：$O(n)$，仅需遍历一次数组。

空间复杂度：$O(1)$，无需额外存储空间。

11. Container With Most Water

原题链接

题目描述

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the i^th line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

Constraints:

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

解题方法

要解决这个问题，我们可以使用双指针的做法。基本思路是从数组的两端开始，计算两个指针之间的容器面积，根据指针所指向的线的高度来判断移动哪个指针。

具体步骤如下：

  1. 初始化两个指针，左指针 left 指向数组的开始，右指针 right 指向数组的末尾；初始化一个返回值用于存储最大面积。
  2. 计算当前 left 和 right 指针形成的容器的面积 area：
    • area = (right - left) * min(height[left], height[right])。
  3. 更新最大面积。
  4. 比较 height[left] 和 height[right]：
    • 如果 height[left] < height[right]，移动左指针向右（left++），因为需要增加高度较小的一侧。
    • 否则移动右指针向左。
  5. 重复步骤 2~4，直至左右指针相遇（此时底部长度为 0，无面积）。

为什么要向内移动指针？

答：向内移动指针的主要原因是寻找可能的更大容器，当前指针所指的两条线决定了容器的高度与宽度，移动指针可以帮助找到可能的更高的线，从而增加面积。并且移动指针能够有效避免重复计算已经确定面积的容器，快速找到潜在的更大面积。

代码实现

Python版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def maxArea(self, height: List[int]) -> int:
        left, right, ans = 0, len(height) - 1, 0

        while left < right:
            current_area = min(height[left], height[right]) * (right - left)
            ans = max(current_area, ans)

            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        
        return ans

Java版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int maxArea(int[] height) {
        int ans = 0, left = 0,right = height.length - 1;
        while(left < right)
        {
            int area = (right - left) * Math.min(height[left], height[right]);
            ans = Math.max(ans, area);
            if(height[left]<height[right])
                left++;
            else 
                right--;
        }
        return ans;
    }
}

复杂度分析

时间复杂度：$O(n)$，仅需遍历一次数组。

空间复杂度：$O(1)$，无需额外存储空间。

15. 3Sum

原题链接

题目描述

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Constraints:

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

解题方法

本题要求我们在数组中找出所有和为 0 的三个数，要求三元组不能够重复。

由于给出的数组并不是单调递增的，我们可以先将数组排序。

为了方便定位，遍历数组，将遍历到的第一个数作为「锚点」，在「锚点」之后的部分用两个指针分别指向最左侧（最小值）以及最右侧（最大值），移动后两个指针来寻找剩余两个数。

这与1. Two Sum的双指针解法思路相像。

假设「锚点」下标为 i，遍历过程：

  1. 如果 i > 0 且 nums[i] == nums[i - 1]，则说明 nums[i] 的结果已经由相同的 nums[i - 1] 加入到结果中，跳出此次循环过程。
  2. 剩余部分的左指针 left 和 right 分别为 i + 1 以及 len(nums) - 1，当 left < right 时，开始如下步骤：
    • 记录当前三数和为 current_sum，current_sum = nums[i] + nums[left] + nums[right]。
    • current_sum > 0，右指针值偏大，右指针移动减少和。
    • current_sum < 0，左指针值偏小，左指针移动增加和。
    • current_sum == 0，说明找到一个合适的三元组，加入到结果中。进行去重部分，移动 left 和 right 的直到不出现相同的数字。

优化部分：

  • 如果 nums[i] > 0，此时后面的数不可能和为 0，提前结束。
  • 如果 nums[i] + nums[-2] + nums[-1] < 0，则说明在这个循环中不可能出现和为 0 的三元组，因为最大的两个值和「锚点」的和都不大于 0。

代码实现

Python版本：

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
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        # 首先对数组进行排序
        nums.sort()
        result = []

        # 遍历数组
        for i in range(len(nums) - 2):
            # 如果当前数大于0，后面的数不可能和为0，提前结束
            if nums[i] > 0:
                break
            # 去重：跳过重复的数字
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            # 优化
            if nums[i] + nums[-2] + nums[-1] < 0:
                continue
            left, right = i + 1, len(nums) - 1
            
            while left < right:
                current_sum = nums[i] + nums[left] + nums[right]
                
                if current_sum < 0:
                    left += 1  # 和小于0，移动左指针增加和
                elif current_sum > 0:
                    right -= 1  # 和大于0，移动右指针减少和
                else:
                    # 找到一个三元组
                    result.append([nums[i], nums[left], nums[right]])
                    
                    # 去重：跳过相同的数字
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1
                    
                    left += 1
                    right -= 1

        return result

Java版本：

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
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        // 首先对数组进行排序
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        int n = nums.length;
        // 遍历数组
        for(int i = 0; i < n - 2; i++)
        {
            // 如果当前数大于0，后面的数不可能和为0，提前结束
            if(nums[i] > 0) break;
            // 去重：跳过重复的数字
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            // 优化
            if (nums[i] + nums[n - 2] + nums[n - 1] < 0) continue;
            int j = i + 1, k = n - 1;
            while (j < k) {
                int s = nums[i] + nums[j] + nums[k];
                if (s > 0) --k; // 和大于0，移动右指针减少和
                else if (s < 0) ++j; // 和小于0，移动左指针增加和
                else {
                    ans.add(List.of(nums[i], nums[j], nums[k])); // 找到一个三元组
                    for (++j; j < k && nums[j] == nums[j - 1]; ++j); // 跳过重复数字
                    for (--k; k > j && nums[k] == nums[k + 1]; --k); // 跳过重复数字
                }
            }
        }
        return ans;
        }
    }

复杂度分析

时间复杂度：$O(n^2)$，其中 $n$ 为 $nums$ 的长度，排序 $O(nlogn)$。

空间复杂度：$O(1)$，无需额外存储空间。

42. Trapping Rain Water

原题链接

题目描述

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Constraints:

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

解题方法

题目大意为给你一个数组，数组内的值代表路面高度，求水坑能装多少水。

这题与上边的11题方法类似，可以使用双指针解决，但是需要注意的是，这道题目的「墙壁」构成地面高度的一部分，而11题中只需要找到两个边界，不会考虑「墙壁」对水体积的影响。

而这道题的双指针，需要采用的策略一样是移动更矮的墙壁，移动的另一侧必然会存在比它更高的墙壁。

如果更高的墙壁移动，而又找不到更高的值就没法计算了。

双指针相向移动的同时，记录遍历的墙高。如果存在更高的墙壁，更新最高高度；如果没有就把最高高度减去地面高度，就能够得出水的体积。

代码实现

Python版：

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
class Solution:
    def trap(self, height: List[int]) -> int:
        # 初始化左右指针
        left, right = 0, len(height) - 1
        # 左右两侧的最高柱子高度
        left_max, right_max = 0, 0
        # 储存雨水的总量
        water = 0

        # 当左指针小于右指针时继续循环
        while left < right:
            # 如果左侧的柱子高度小于右侧的柱子高度
            if height[left] < height[right]:
                # 如果当前柱子的高度大于左侧最高柱子的高度，更新左侧最高高度
                if height[left] >= left_max:
                    left_max = height[left]
                else:
                    # 否则，计算当前柱子上方可以储存的水量
                    water += left_max - height[left]
                # 移动左指针向右
                left += 1
            else:
                # 如果右侧的柱子高度小于或等于左侧的柱子高度
                if height[right] >= right_max:
                    right_max = height[right]
                else:
                    # 否则，计算当前柱子上方可以储存的水量
                    water += right_max - height[right]
                # 移动右指针向左
                right -= 1
                
        return water

Java版：

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
class Solution {
    public int trap(int[] height) {
        int n = height.length;
        if(n <= 2){
            return 0;
        }
        int left = 0;
        int right = n - 1;
        int total = 0;
        int maxLeft = 0;
        int maxRight = 0;
        while(left < right){
            if(height[left] < height[right]){
                if(height[left] >= maxLeft){
                    maxLeft = height[left++];
                }
                else{
                    total += maxLeft - height[left++];
                }
            }
            else{
                if(height[right] >= maxRight){
                    maxRight = height[right--];
                }
                else{
                    total += maxRight - height[right--];
                }
            }
        }
        return total;
    }
}

复杂度分析

时间复杂度：$O(n)$，只需要遍历一次数组。

空间复杂度：$O(1)$，没有额外的空间。

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://blog.skyheart.moe/posts/6cef87b0/

更新于：2024年9月30日

双指针

评论