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;}
}