LeetCode Hot 100：1.两数之和、49.字母异位词分组、128.最长连续序列、283.移动零、11.盛水最多的容器

一、1.两数之和

哈希表的应用，哈希表可以快速查找是否存在某个值。

需要索引要设为值，以数值为key，用containsKey()查找是否存在，用get()获取下标。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i=0 ; i<nums.length ; i++){
            map.put(nums[i],i);
        }
        for(int i=0 ; i<nums.length ; i++){
            int temp = target-nums[i];
            if(map.containsKey(temp) && map.get(temp) != i){
                return new int[]{map.get(temp),i};
            }
        }
        return null;
    }
}

可以将判断和放入元素的过程通过一个元素实现（同时能解决不能使用重复元素的问题）

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

二、49.字母异位词分组

由于字母异位词在对字符进行排序后结果相同，所以可以利用hashmap，以排序后的字符串为键，原字符串为值的集合中的元素，对原字符串数组进行遍历，依次放入hashmap集合中。

需要注意的点：

排序sort是工具类Arrays中的，没有返回值！对数组本身操作！

getOrDefault方法，

values方法取所有值，返回的是Collection<>

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String,List<String>> map = new HashMap<>();
        for(String str : strs){
            char[] ch = str.toCharArray();//转为字符数组
            Arrays.sort(ch);              //排序
            String key = new String(ch);  //转化为字符串（也是集合的key）
            List<String> list = map.getOrDefault(key , new ArrayList<>());
            list.add(str);
            map.put(key , list);
        }
        return new ArrayList<List<String>>(map.values());
    }
}

三、128.最长连续序列

将数组放入HashSet，注意遍历时用set集合遍历就不会超时

判断num-1如果不在集合中，那么该元素就是连续数字的起始数，则while循环判断num+1是否存在，记录最长的连续数

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<Integer>();
        for (int num : nums) set.add(num);      
        int res = 0;
        for (int num : set) {
            if (!set.contains(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;
                while (set.contains(currentNum + 1)) {
                    currentNum += 1;
                    currentStreak += 1;
                }
 
                res = Math.max(res, currentStreak);
            }
        }
        return res;
    }
}

四、283.移动零

class Solution {
    public void moveZeroes(int[] nums) {
        int n = nums.length;
        int left = 0;
        int right = 0;
        while(right<n){
            if(nums[right]!=0){
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                left++;
            }
            right++;
        }      
    }
}

五、11.盛水最多的容器

在每一步中，比较 height[left] 和 height[right] 的大小：

• 如果 height[left] < height[right]：
  • 这意味着当前容器的高度由 height[left] 决定。因为容器的水量取决于较短的那条垂线，此时如果将 right 指针向左移动，容器的宽度会减小，而高度最多只能保持不变（因为 height[left] 是较短的那条），所以水量只会减小。
  • 因此，为了有可能找到更大的水量，我们将 left 指针向右移动，这样有可能找到更高的垂线，从而增加容器的高度。
• 如果 height[left] >= height[right]：
  • 此时容器的高度由 height[right] 决定。同理，如果将 left 指针向右移动，容器的宽度会减小，而高度最多只能保持不变，水量只会减小。
  • 所以，我们将 right 指针向左移动，以尝试找到更高的垂线，增加容器的高度。

class Solution {
    public int maxArea(int[] height) {
        int left = 0;
        int right = height.length-1;
        int res = 0;
        while(left<right){
            if(height[left]<height[right]){
                res = Math.max(res, (right - left) * height[left]);
                left++;
            }else if(height[left]>=height[right]){
                res = Math.max(res, (right - left) * height[right]);
                right--;
            }
        }
        return res;
    }
}