跳至主要內容

hot100-02-双指针

holic-x...大约 13 分钟算法算法

难度说明：🟢简单🟡中等🔴困难

hot100-02-双指针

🟢01-移动零（283）

1.题目内容

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

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

2.题解思路

  • 如果是最简单的做法是循环遍历数组，然后判断非0数依次插入新数组，统计0的个数，然后数组尾部补齐0
  • 类似的，如果不引入新的数组则循环遍历、覆盖、补0即可

👻方法1（✅）：

​ 已知移动的是0，此处采用覆盖、补0的思路，定义一个current指针，用于记录当前覆盖的位置，遍历数组过程中如果非0则进行覆盖、指针后移，最后一步再从当前覆盖位置开始到数组长度位置进行补0

public class Solution283 {
    public void moveZeroes(int[] nums) {
        // 循环遍历，依次进行覆盖（指针记录当前覆盖的位置，指针后面的用0补齐）
        int current = 0;
        for (int i = 0; i < nums.length; i++) {
            if(nums[i]!=0){
                // 非0，覆盖
                nums[current] = nums[i];
                // 当前覆盖位置后移
                current++;
            }
        }
        // 从当前指针位置补0
        for(int i=current;i<nums.length;i++){
            nums[i]=0;
        }
    }
}

复杂度分析

  • 时间复杂度：
  • 空间复杂度：

思路2：双指针

​ 官方推荐的是双指针 + 交换思路

class Solution {
    public void moveZeroes(int[] nums) {
        int n = nums.length, left = 0, right = 0;
        while (right < n) {
            if (nums[right] != 0) {
                swap(nums, left, right);
                left++;
            }
            right++;
        }
    }

    public void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}

3.复盘

双指针思路

  • 思考为什么要用双指针：引入双指针的思路在于，在不开设新的数组空间的情况下，实际就是把数组劈成两半，前面一段存储非0元素、后面一段存储0元素，因此引入双指针的思路来进行设计，但考虑到这个过程中实际上并不知道0的个数有多少，因此问题在于怎么确定这个数组的"分界线"，因此转换思路，可以分别从数组的两端出发，当两个指针相遇的时候就是这个数组的分界线。但这种方向会存在一个问题，即从两端开始分别遍历并不能保证原有元素的有序性，例如前面的非0数字会被先置换
    • 在双指针移动的过程中，为了避免概念混淆，只需要以一端元素判断为基础，例如判断left是否为0的前置条件下再去判断right为0的情况
      • left 为 0：
        • right 为 0：right --（相当于往前给右侧找一个不为0的数）
        • right 不为 0：替换，然后指针互相靠拢
      • left 不为0：left ++ （相当于往前给左侧找一个为0的数）
  • 双指针起始位置为什么都从0开始：因为在上述方案的设计中，如果采用相向的指针，则无法保证数组元素的顺序，因此此处考虑使用同向的指针去做
    • 起始位置：两个指针都从0开始
    • 终止条件：右边存的是0元素，因此判断依据是当right走到n的位置表示遍历结束
    • 内部设计：如果出现非0元素则交换当前left、right的值并让左指针往前，如果出现0元素则右指针往前
	/**
     * 双指针 + 交换的思路
     * 因为不能用到额外的数组空间，因此此处采用双指针思路，左指针记录非0元素存储的位置；右指针记录0元素存储的位置
     * 如果左指针指向元素不为0则左指针继续向前，如果指向元素为0则和右指针所在位置元素进行交换，直到两个指针相遇
     * 需注意如果左右指针元素都为0的话，则右指针要继续往前（否则0 0交换没有意义了）
     * PS:此思路是用两个反方向的指针来做的，虽然思路ok，但是数组元素的顺序会被打乱
     * @param nums
     */
    public void moveZeroes(int[] nums) {
        // 定义双指针
        int left = 0, right = nums.length - 1;
        // 指针相遇循环结束
        while (left <= right) {
            // 以左指针为基础判断，如果左指针元素为0需考虑交换（还需考虑右指针是否为0）
            if (nums[left] == 0) {
                // 判断右指针是否为0
                if (nums[right] == 0) {
                    right--; // 右指针为0，则右指针向前
                } else {
                    // 交换左右指针
                    int temp = nums[left];
                    nums[left] = nums[right];
                    nums[right] = temp;
                    // 左右指针靠拢
                    left++;
                    right--;
                }
            } else {
                // 考虑左指针不为0的情况，则左指针继续往前即可
                left++;
            }
        }
    }

// 双指针（同向）+交换
public void moveZeroes(int[] nums) {
    int n = nums.length, left = 0, right = 0;
    // 右边存的是0元素，因此判断依据是当right走到n的位置表示遍历结束
    while (right < n) {
        if (nums[right] != 0) {
            swap(nums, left, right);
            left++;
        }
        right++;
    }
}

public void swap(int[] nums, int left, int right) {
    int temp = nums[left];
    nums[left] = nums[right];
    nums[right] = temp;
}

🟡02-盛最多水的容器（11）

1.题目内容

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

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

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

​ **说明：**不能倾斜容器

2.题解思路

​ 首先理解题目思路，先得出盛水面积的计算公式：

image-20240919163202069

​ 可以看到，在宽度一定的条件下，盛水面积的大小是取决于短板高度的S(i,j)=min(h[i],h[j])*(j-i)，那么此处问题在于分析应该移动短板还是长板？结合公式分析可知，移动过程中(j-i)肯定是减小的，因此主要看min(h[i],h[j])

  • 如果移动短板，min(h[i],h[j])可能会变大，因此下个水槽的面积可能会增大（移动短板，移动时高度变大的话可能得到乘积变大）

  • 如果移动长板，min(h[i],h[j])不变或变小，因此下个水槽的面积一定会变小（移动长板，移动时会替换掉长板，）

    基于上述分析，因此定义双指针是通过移动短边来实现，当指针相遇则计算结束，得到最大的值

算法核心：初始化双指针、循环收窄（更新最大面积res、选定短板进行移动）、返回最大面积值res

public class Solution {
    /**
     * 思路：双指针（x缩小的时候要尽可能找长的柱子才能使得存储水量变大）
     * 因此可以将题意简化为双指针判断短边并移动短边，因为只有移动短边才有可能使得在x缩小的时候，会不会找到一条更高的柱子
     */
    public int maxArea(int[] height) {
        int left = 0, right = height.length - 1;// 定义双指针记录选择的柱子
        int max = 0; // 定义面积最大值用作记录
        // 当指针相遇循环结束
        while (left < right) {
            // 记录当下的最大值，并移动短边
            if (height[left] < height[right]) {
                max = Math.max(max, height[left] * (right - left)); // 装水遵循木桶效应
                left++; // 移动短边，寻找下一个可能使得max变大的边
            } else if (height[left] >= height[right]) {
                max = Math.max(max, height[right] * (right - left));// 装水遵循木桶效应
                right--; // 移动短边，寻找下一个可能使得max变大的边
            }
        }
        // 返回结果
        return max;
    }
}

简化版本写法

public class Solution11 {

    public int maxArea(int[] height) {
        // 双指针：定义左侧指针、右侧指针、盛水面积
        int i = 0, j = height.length - 1, res = 0;
        // 当两个指针相遇则停止，在比较过程中计算面积大小（宽度一定的情况下，面积大小取决于短板高度）
        while(i < j) {
            // 比较当前指针对应的柱高度，移动短板一侧，获取较大的res
            res = height[i] < height[j] ?
                    Math.max(res, (j - i) * height[i++]):
                    Math.max(res, (j - i) * height[j--]);
        }
        return res;
    }

    public static void main(String[] args) {
        Solution11 s = new Solution11();
        int[] height = {1,8,6,2,5,4,8,3,7};
        System.out.println(s.maxArea(height));
    }

}

3.复盘

🟡03-三数之和（15）

1.题目内容

​ 提供一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组

2.题解思路

思路1：排序+双指针（超时）

​ 三数之和题解参考open in new window

​ 暴力拆解：循环嵌套，暴力检索校验

​ 所谓三元组（三数之和为0），那么其有相应的规律（3个数字都是0，3个数字中有正有负），基于此可以将数组进行排序，循环遍历排序后的数组元素，然后通过左右移动指针来获取到匹配的元素（因为数组已经有序，所以可以先定a，然后再根据指针选定b、c的值，通过移动指针让整体值趋于0，当两个指针相遇则本轮校验结束）

  • 初始化：i（指向当前元素），p（指向i+1位置），q指向数组末尾
  • 校验三元组、去重：计算当前值，将其与0进行比较，基于此确认应该移动哪个指针，让三元组的值趋向0，直到p、q指针相遇，本次遍历结束，且在这个过程中需要进行去重处理
    • 三元组sum值校验
      • 【如果sum等于0】：满足条件，将其放入result结果集
        • 去重：因为元素本身有序，所以此处可以使用List<Integer>收纳三元组，然后借助List的contains方法进行校验，有重复则不加入result结果集
      • 【如果sum大于0】：向左移动 q 指针，q 会变小，让sum趋于0
      • 【如果sum小于0】：向右移动 p 指针，p 会变大，让sum趋于0
/**
 * 三数之和
 * 核心：找出符合条件的三元组
 */
public class Solution15 {

    public List<List<Integer>> threeSum(int[] nums) {
        // 定义结果集
        List<List<Integer>> result = new ArrayList<>();
        // 对数据进行排序
        Arrays.sort(nums);
        // 循环遍历进行校验
        for (int i = 0; i < nums.length; i++) {
            // 定义双指针
            int p = i + 1, q = nums.length - 1;
            // 双指针相遇则本次遍历结束
            while (p < q) {
                // 校验sum值
                int sum = nums[i] + nums[p] + nums[q];
                if (sum == 0) {
                    // 满足条件则加入结果集 result.add(Arrays.asList(nums[i], nums[p], nums[q]));
                    // 去重操作
                    List<Integer> target = Arrays.asList(nums[i], nums[p], nums[q]);
                    if(!result.contains(target)) {
                        result.add(target);
                    }
                    // 移动双指针
                    p++;
                    q--;
                } else if (sum < 0) {
                    // 向右移动p指针，让p变大，让sum趋于0
                    p++;
                } else if (sum > 0) {
                    // 向左移动q指针，让q变小，让sum趋于0
                    q--;
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {-1, 0, 1, 2, -1, -4};
        Solution15 solution = new Solution15();
        System.out.println(solution.threeSum(nums));
    }

}

补充说明

​ 此处有一个设计很巧妙的点在于三元组指针的初始化选择：

  • 方案1：i; left = i+1; right = length -1;
  • 方案2：i; left = 0; right = length -1;

​ 两种方案都能实现找出所有的三元组，但是区别在于方案1是能够在排序的基础下保证有序性（非常方便地用于后面的去重判断）；而方案2是类似中规中矩的夹心思路，始终让指针从两端出发，思路清晰，但是在循环中去重则略显疲态（需处理去重逻辑）

3.复盘

优化解法

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length && nums[i] <= 0; i++) {
            if (i > 0 && nums[i - 1] == nums[i]) continue;
            int p = i + 1, q = nums.length - 1;
            while (p < q && nums[q] >= 0) {
                int iv = nums[i], qv = nums[q], pv = nums[p], sum = iv + pv + qv;
                if (sum == 0) result.add(Arrays.asList(iv, pv, qv));
                if (sum > 0) while (q > 0 && nums[q] == qv) q--;
                else while (p < nums.length - 1 && nums[p] == pv) p++;
            }
        }
        return result;
    }
}

🔴04-接雨水（42）

1.题目内容

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

image-20241014222302496

2.题解思路

​ 解答思路：动态规划、双指针、单调栈

思路1：暴力枚举（动态规划优化时间复杂度）

​ 每个桶可以接的雨水量：l_max （当前元素的最大前缀，包括其本身）、r_max（当前元素的最大后缀，包括其本身），每个桶接的雨水量为min(l_max[i],r_max[i])-height[i]（水往低处流）

  • 第1次遍历：计算前缀最大值：遍历一遍数组，计算每个元素所在位置的最大前缀（从前往后遍历，比较范围包括其本身）
  • 第2次遍历：计算后缀最大值：遍历一遍数组，计算每个元素所在位置的最大后缀（从后往前遍历，比较范围包括其本身）
  • 第3次遍历：再遍历一遍数组，计算每个**"桶"**接的雨水min{l_max[i],r_max[i]} - height[i]，然后进行累加
/**
 * 42.接雨水
 */
public class Solution1 {

    /**
     * 思路:将接雨水转化为计算各个"桶"装的雨水之和
     * 思考每个桶的接水量如何计算：
     * l_max 表示当前桶的最大前缀（从前往后比较，包括其本身） 可以通过一次正序遍历获取
     * r_max 表示当前桶的最大后缀（从后往前比较，包括其本身） 可以通过一次倒序遍历获取
     * 当前桶的接水量为min(l_max[i],r_max[i])-height[i] 再次遍历计算结果
     */
    public int trap(int[] height) {
        // 定义返回结果
        int res = 0;

        // 存储数组长度值
        int len = height.length;

        // 1.正序遍历：计算每个桶的最大前缀（包括其本身）
        int[] l_max = new int[len];
        l_max[0] = height[0]; // 初始化第一个元素
        for (int i = 1; i < len; i++) {
            l_max[i] = Math.max(height[i], l_max[i - 1]); // 最大前缀：前一个元素存储了前[i-1]位置元素的最大前缀，此处将其和自身进行比较即可
        }

        // 2.倒序遍历：计算每个桶的最大后缀（包括其本身）
        int[] r_max = new int[len];
        r_max[len - 1] = height[len - 1]; // 从后往前初始化元素
        for (int i = len - 2; i >= 0; i--) {
            r_max[i] = Math.max(height[i], r_max[i + 1]);
        }

        // 3.遍历数组：计算每个桶的接水量进行累加
        for (int i = 0; i < len; i++) {
            res += Math.min(l_max[i], r_max[i]) - height[i];
        }

        // 返回结果
        return res;
    }
}

思路2：双指针

3.复盘

0  字
评论
  • 按正序
  • 按倒序
  • 按热度
Powered by Waline v3.1.3
一人の境 Copyright © 2019-未知 holic-x
Copyright © 2025 holic-x