当前位置：首页 > article >正文

前端力扣刷题 | 2：hot100之双指针

article 2025/1/30 22:24:26

283. 移动零

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

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

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

法一：

var moveZeroes = function(nums) {
    let count = 0;   // 存储 0 的个数
    for(let i=0;i<nums.length;i++){
        if(nums[i]===0){
            count++;
            nums.splice(i,1);
            i--;
        }
    }
    for(let i=0;i<count;i++){
        nums.push(0);
    }
};

时间复杂度：O(n²)（由于 splice 的代价高昂）。
空间复杂度：O(1)。

法二：双指针

var moveZeroes = function(nums) {
    let slow = 0;
    for(let fast=0;fast<nums.length;fast++){
        if(nums[fast]!==0);{
            nums[slow] = nums[fast];
            slow++;
        }
    }
    nums.fill(0,slow);
};

时间复杂度：O(n)
空间复杂度：O(1)

11. 盛最多水的容器

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

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

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

说明：你不能倾斜容器。
在这里插入图片描述

解法：

每次计算当前两指针间的容积。
比较两指针对应的高度，移动较矮的一边（试图找到更高的垂直线以可能增加容积）。

var maxArea = function(height) {
    let res=0;
    let left = 0, right = height.length-1;
    while(left<right){
        let water = (right-left)*Math.min(height[left],height[right]);
        res = Math.max(res,water);
        if(height[left]<=height[right]){
            left++;
        }else{
            right--;
        }
    }
    return res;
};

15. 三数之和

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

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

示例：

输入：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] 。
注意，输出的顺序和三元组的顺序并不重要。

解法：

排序：nums.sort((a, b) => a - b) 是一个升序排序函数，便于后续双指针的使用。
遍历和双指针：
- 遍历数组时，通过 nums[i] 固定一个数。
- 使用双指针 left 和 right 在 nums[i] 之后的部分查找两个数。
避免重复：
- 在外层循环中，如果当前值与上一个值相同，跳过该次循环。
- 在内部查找过程中，跳过重复的 left 和 right 值。

function threeSum(nums) {
    const res = [];
    nums.sort((a, b) => a - b); // 排序数组
    
    for (let i = 0; i < nums.length; i++) {
        // 如果当前数大于 0，则后面的数不可能满足条件，直接退出循环
        if (nums[i] > 0) break;

        // 跳过重复的固定数
        if (i > 0 && nums[i] === nums[i - 1]) continue;

        let left = i + 1, right = nums.length - 1;
        while (left < right) {
            const sum = nums[i] + nums[left] + nums[right];
            if (sum === 0) {
                res.push([nums[i], nums[left], nums[right]]);
                
                // 跳过重复的左指针值
                while (left < right && nums[left] === nums[left + 1]) left++;
                // 跳过重复的右指针值
                while (left < right && nums[right] === nums[right - 1]) right--;

                // 移动指针
                left++;
                right--;
            } else if (sum < 0) {
                // 如果和小于 0，左指针右移
                left++;
            } else {
                // 如果和大于 0，右指针左移
                right--;
            }
        }
    }
    
    return res;
}