「🦆TSK的博客」

Appearance

On this page

双指针 ​

盛水最多的容器 ​

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

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

设两指针 i , j , 指向的水槽板高度分别为 h[i], h[j],此状态下水槽面积为 S(i,j)。由于可容纳水的高度由两板中的 短板 决定，因此可得如下 面积公式 ：

S(i,j)=min(h[i],h[j])×(j−i)

在每个状态下，无论长板或短板向中间收窄一格，都会导致水槽 底边宽度 −1-1−1​ 变短：

  • 若向内 移动短板 ，水槽的短板 min(h[i],h[j]) 可能变大，因此下个水槽的面积 可能增大 。
  • 若向内 移动长板 ，水槽的短板 min(h[i],h[j])​ 不变或变小，因此下个水槽的面积 一定变小 。
ts
function maxArea(height: number[]): number {
    let i = 0, j = height.length - 1, max = 0;
    while (i <= j) {
        // 右边板子更短
        if (height[i] > height[j]) {
            max = Math.max((j - i) * height[j], max)
            j--;
        } else {
            max = Math.max((j - i) * height[i], max)
            i++;
        }
    }
    return max
};

三数之和 ​

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组

  • 给定数组 nums = [-1, 0, 1, 2, -1, -4]，输出： [ [-1, 0, 1], [-1, -1, 2] ]

由于是需要不重复,所以需要排序
而且对于这种多个数的组成的结果,一定要固定几位,然后只去移动两位

去重逻辑 ​

其实主要考虑三个数的去重。 a, b ,c, 对应的就是 nums[i]，nums[left]，nums[right]

a 如果重复了怎么办，a 是 nums 里遍历的元素，那么应该直接跳过去。但这里有一个问题 ，是判断 nums[i] 与 nums[i + 1]是否相同，还是判断 nums[i] 与 nums[i-1] 是否相同 。

🔥 其实可以这样思考：

当 left 前进的时候,如果遍历到了 left 的时候，那么 left - 1 必然已经取过了，所以只需要判断 num[left] == num[left - 1],就可以跳过重复

同理的，当 right 前进的时候，如果遍历到了 right 的时候，那么 right + 1 必然已经取过了，所以只需要判断 num[right] == num[right + 1],就可以跳过重复

ts
function threeSum(nums: number[]): number[][] {
    nums.sort((a,b)=>a-b);

    let result: number[][] = [];
    for (let i = 0; i < nums.length - 2; i++) {

    // 不能 == 0,因为有 [0,0,0] 的情况
        if (nums[i] > 0) {
            return result;
        }

        if(nums[i] == nums[i-1])continue;

        let l = i + 1, r = nums.length - 1;
        let current = nums[i];

        while (l < r) {
            let total = current + nums[l] + nums[r];

            if (total == 0) {
                result.push([current, nums[l], nums[r]])

                l++
                r--

                while (l<r && nums[l] == nums[l - 1]) {
                    l++
                }

                while (l<r && nums[r] == nums[r + 1]) {
                    r--
                }

            } else if (total > 0) {
                r--
            } else {
                l++
            }
        }
    }
    return result
};

Updated at: