leetcode刷题记录

原题地址

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

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

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

说明：你不能倾斜容器。

示例 1：

输入：[1,8,6,2,5,4,8,3,7]
输出：49 

解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
示例 2：

输入：height = [1,1]
输出：1

提示：

n == height.length
2 <= n <= 105
0 <= height[i] <= 104

双指针代码

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

    public static int maxArea(int[] height) {
        int l = 0, r = height.length - 1;
        int ans = Integer.MIN_VALUE;
        while (l < r) {
            int areas = Math.min(height[l], height[r]) * (r - l);
            ans = Math.max(ans, areas);
            if (height[l] <= height[r]) {
                ++l;
            } else {
                --r;
            }
        }
        return ans;
    }
}

练习记录

第一次练习时间：2022.02.08 09:44 pm 15：三数之和

原题链接
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

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

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

示例 2：

输入：nums = []
输出：[]

示例 3：

输入：nums = [0]
输出：[]

提示：

0 <= nums.length <= 3000
-105 <= nums[i] <= 105

Java代码

package xyz.fudongyang.classic;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;


public class Lc_15 {
    public static void main(String[] args) {
        int[] arr = {-1, 0, 1, 2, -1, -4};
        System.out.println(threeSum(arr));
    }

    public static List> threeSum(int[] nums) {
        int n = nums.length;
        // 先给数组排序
        Arrays.sort(nums);
        List> ans = new ArrayList<>();

        for (int first = 0; first < n; first++) {

            // 如果不是第一个 需要判断是否和前一个相同 如果相同则不需要重复枚举了
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }

            // c的指针始终是数组的右边界
            int third = n - 1;
            // 这是目标值
            int target = -nums[first];

            for (int second = first + 1; second < n; second++) {
                // 同样的 如果b枚举 也不能相同 相同就不需要重复枚举了
                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    continue;
                }

                // 右侧是最大值 如果b+c小于等于目标值 或者 两个坐标相撞了 就退出
                while (second < third && nums[second] + nums[third] > target) {
                    --third;
                }

                // 坐标相撞情况
                if (second == third) {
                    break;
                }

                // 目标值
                if (nums[second] + nums[third] == target) {
                    List data = new ArrayList<>(3);
                    data.add(nums[first]);
                    data.add(nums[second]);
                    data.add(nums[third]);
                    ans.add(data);
                }
            }
        }

        return ans;
    }
}

第一次练习时间：2022/2/28 下午 09:47