Erlo

hot100之双指针

2025-06-04 18:29:27 发布   20 浏览  
页面报错/反馈
收藏 点赞

移动0(283)

先看代码

class Solution {
    public void moveZeroes(int[] nums) {
        int idx0 = 0;
        for (int idx = 0; idx 
  • 分析

由于仅当 nums[idx] == 0 时 idx0和idx间距会扩大 即有idx0 ~idx 间都为0

idx0用于记录0的起始位置, idx 向前移动发现非0 填入idx0 idx0 向右移动

  • 感悟

双指针通过停一动一, 将两次遍历融合在一次遍历中, 同时维护两个指针, 处理两个数据

盛最多水的容器(011)

先看代码

class Solution {
    public int maxArea(int[] height) {
        int res = 0;
        int lef = 0;
        int rig = height.length - 1;
        while (lef 
  • 分析

容器盛最多水由短板决定, 显然在相同短板下容器越宽越好 所以让左右板从最边缘开始

增大容器容量只能通过寻找更优最短板(lef++ OR rig--), 此时的 trade off 就是容器变窄

  • 感悟

双指针技巧特别适合需要同时考虑多个值的处理场景

三数之和(015)

先看代码

class Solution {
    public List> threeSum(int[] nums) {
        List> res = new ArrayList();
        int n = nums.length;
        Arrays.sort(nums);
        for (int i = 0; i  0)     break;
            if (i > 0 && nums[i] == nums[i-1]) continue;

            int lef = i+1;
            int rig = n-1;
            while (lef  0) rig--;
            }
        }
        return res;
    }
}
  • 分析

分解问题成定一找二 寻找 nums[i] + nums[j] = - nums[k] 且 k

nums[k] 要和 (nums[i] + nums[j]) 为异号, 且当 nums[k] > 0 时结束

k

因为 nums[i] + nums [j] + nums[k] i, j, k 可相互替换

k 枚举了所有 nums[i] OR nums[j] OR nums[k]

先通过 sort 对原数组排序 →(方便去重 | 便于 nums[k] > 0 时结束 )

  • 感悟

写完了两数之和, 第一感觉是要以nums[k]作target , 取nums[i] + nums[j]作两数之和

但分析之后发现 还是用了二分

时间复杂度: 双指针O(n*logn + n²/2 ), hash O(n² + k(n))

双指针有 n²/2 因为只枚举小于0情况, 由实际动态浮动 , 这里就先取个2

k(n)指哈希计算、解决哈希冲突, 及哈希扩容

空间复杂度: 双指针O(1), hash O(n² → 利用hashset去重) 双指针在res中操作, 而hash 还要维护set
另外, hash代码实现比较麻烦 orz

接雨水(042)

先看代码

class Solution {
    public int trap(int[] height) {
        int res = 0;
        int lef = 0;
        int rig = height.length-1;
        int preMax = 0;
        int sufMax = 0;
        while (lef  sufMax ? sufMax - height[rig--] : preMax - height[lef++];
        }
        return res;
    }
}
  • 分析

通过维护全局两侧最高板, 采用了盛最多水的容器(011)的做法 寻找最优短板

对遍历到的块的接水量进行计算

  • 感悟

暂无

登录查看全部

参与评论

评论留言

还没有评论留言,赶紧来抢楼吧~~

手机查看

返回顶部

给这篇文章打个标签吧~

棒极了 糟糕透顶 好文章 PHP JAVA JS 小程序 Python SEO MySql 确认