LeetCode 7 / 100

哈希表、双指针

哈希表
- 两数之和
- 字母异位词分组
- 最长连续序列
双指针
- 移动零
- 盛最多水的容器
- 三数之和
- 接雨水

LeetCode 1.两数之和
LeetCode 49. 字母异位词分组
LeetCode 128. 最长连续序列

LeetCode [283. 移动零](https://leetcode.cn/problems/move-zeroes/?envType=study-plan-v2&envId=top-100-liked) LeetCode [11. 盛最多水的容器](https://leetcode.cn/problems/container-with-most-water/description/?envType=study-plan-v2&envId=top-100-liked) LeetCode [15. 三数之和](https://leetcode.cn/problems/3sum/description/?envType=study-plan-v2&envId=top-100-liked) LeetCode [42. 接雨水](https://leetcode.cn/problems/trapping-rain-water/description/?envType=study-plan-v2&envId=top-100-liked)

哈希表

两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

哈希map

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];
        HashMap<Integer, Integer> hm = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (hm.containsKey(nums[i])) {
                result[0] = hm.get(nums[i]);
                result[1] = i;
            }
            hm.put(target - nums[i], i);
        }
        return result;
    }
}

字母异位词分组

给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。

字母异位词是由重新排列源单词的所有字母得到的一个新单词。

排序，哈希map
互为字母异位词的两个字符串包含字母相同，排序之后的字符串一定相同，可以将排序后的字符串作为哈希表的键。

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String, List<String>> hm = new HashMap<>();

        for (String str : strs) {
            char[] array = str.toCharArray();
            Arrays.sort(array);
            String key = new String(array);
            List<String> list = hm.getOrDefault(key, new ArrayList<String>());
            list.add(str);
            hm.put(key, list);
        }

        return new ArrayList<List<String>> (hm.values());
    }
}

最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

这个题要求了时间复杂度为 O(n)
因此不能用排序了
用哈希表存储，这样查看一个数是否存在就不用遍历数组了，优化到 O(1)
然后找最长数字连续序列的起始位置，这里就是1 ，随后只要判断 2， 3， 4 … 在不在哈希表里即可，在内层用 while 循环遍历，时间复杂度为 O(n)
那外层就不能是 O(n) 了，
因此外层需要有个判断条件再过滤一下
也就是判断哈希表里（当前值 - 1 ）是否存在，如果不存在，说明当前值可能是最长数字连续序列的第一位，否则，就不是初始位置，那肯定不是最大长度。
用一个 length 来接受这个长度， Math.max(length, currentLength)

class Solution {
    public int longestConsecutive(int[] nums) {
        HashSet<Integer> hs = new HashSet<>();
        for (Integer num : nums) {
            hs.add(num);
        }

        int length = 0;
        for (int num : nums) {
            if (!hs.contains(num - 1)) {
                int currentNum = num;
                int currentLength = 1;

                while (hs.contains(currentNum + 1)) { // 注意这里是当前值+1
                    currentNum++;
                    currentLength++;
                }
                length = Math.max(length, currentLength);
            }
        }
        return length;
    }
}

双指针

移动零

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

class Solution {
    // 双指针
    public void moveZeroes(int[] nums) {
        int slow = 0;
        for (int fast = 0; fast < nums.length; fast++) {
            if (nums[fast] != 0) {
                nums[slow] = nums[fast];
                slow++;
            }
        }
        for (;slow < nums.length; slow++) {
            nums[slow] = 0;
        }
    }
}

盛最多水的容器

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

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

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

说明：你不能倾斜容器。

双指针往内收缩的依据是哪个 height 小，哪个往里缩

在这里插入图片描述

class Solution {
    public int maxArea(int[] height) {
        int i = 0, j = height.length - 1, res = 0;
        while (i < j) {
            res = height[i] < height[j] ?
                Math.max(res, (j - i) * height[i++]):
                Math.max(res, (j - i) * height[j--]);
        }
        return res;
    }
}

三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

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

第二次做这个题，忘记考虑去重，双指针分配不对
三个数，一个数是 i ，一个是 left = i + 1 ，一个是 right = nums.length - 1 ， while 循环，判断，去重

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        Arrays.sort(nums);

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                return list;
            }

            // 去重
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            int left = i + 1;
            int right = nums.length - 1;
            while (left < right) {
                if (nums[i] + nums[left] + nums[right] < 0) {
                    left++;
                } else if (nums[i] + nums[left] + nums[right] > 0) {
                    right--;
                } else {
                    list.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    // 去重
                    while (right > left && nums[right] == nums[right - 1]) right--;
                    while (right > left && nums[left] == nums[left + 1]) left++;
                    right--;
                    left++;
                }
            }
        }
        return list;
    }
}

接雨水

class Solution {
    // 动态数组
    public int trap(int[] height) {
        int res = 0;

        int[] maxLeft = new int[height.length];
        int[] maxRight = new int[height.length];
        maxLeft[0] = 0;
        maxRight[height.length-1] = 0;
        for (int i = 1; i < height.length; i++) {
            maxLeft[i] = Math.max(maxLeft[i-1], height[i-1]);
        }
        for (int i = height.length-2; i >= 0; i--) {
            maxRight[i] = Math.max(maxRight[i+1], height[i+1]);
        }
        for (int i = 1; i < height.length - 1; i++) {
            if (Math.min(maxLeft[i], maxRight[i]) > height[i]) {
                res += Math.min(maxLeft[i], maxRight[i]) - height[i];
            } 
        }
        return res;
    }
}

// 双指针
class Solution {
    public int trap(int[] height) {
        int res = 0;
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0;
        while (left < right) {
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);

            if (leftMax < rightMax) {
                res += leftMax - height[left];
                left++;
            } else {
                res += rightMax - height[right];
                right--;
            }
        }
        return res;
    }
}