LeetCode_Array

[dailiuyang123]

leetcode 数组类

[dailiuyang123]

题目地址： https://leetcode-cn.com/problems/container-with-most-water/

[11. 盛最多水的容器]

// 给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
// 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
// 返回容器可以储存的最大水量。

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

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

[dailiuyang123]

题目地址： https://leetcode-cn.com/problems/3sum/

15. 三数之和

// 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
//
// 注意：答案中不可以包含重复的三元组。

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

public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums.length < 3) {
            return result;
        }
        List<Integer> zheng = new ArrayList<>();
        List<Integer> fu = new ArrayList<>();
        Set<String> strs=new HashSet<>();

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= 0) {
                zheng.add(nums[i]);
            } else {
                fu.add(nums[i]);
            }
        }
        Collections.sort(zheng);
        Collections.sort(fu);
        if(zheng.size()>=3 && zheng.get(2)==0){
            result.add(Arrays.asList(new Integer[] {0, 0, 0}));
        }

        // 正数为1个

        for (Integer z : zheng) {
            // 双指针
            int l = 0, r = fu.size() - 1;
            while (l < r) {
                if (fu.get(l) + fu.get(r) + z == 0) {
                    Integer[] cas = {fu.get(l), fu.get(r), z};
                    List<Integer> ints = Arrays.asList(cas);
                    if(!strs.contains(ints.toString())){
                        result.add(ints);
                        strs.add(ints.toString());
                    }
                    r--;
                    l++;
                } else if (fu.get(l) + fu.get(r) + z > 0) {
                    r--;
                } else {
                    l++;
                }
            }
        }
        // 负数为1个

        for (Integer f : fu) {
            // 双指针
            int l = 0, r = zheng.size() - 1;
            while (l < r) {
                if (zheng.get(l) + zheng.get(r) + f == 0) {
                    Integer[] cas = {f, zheng.get(l), zheng.get(r)};
                    List<Integer> ints = Arrays.asList(cas);
                    if(!strs.contains(ints.toString())){
                        result.add(ints);
                        strs.add(ints.toString());
                    }
                    r--;
                    l++;
                } else if (zheng.get(l) + zheng.get(r) + f > 0) {
                    r--;
                } else {
                    l++;
                }
            }
        }

        return result;
    }