LC-两数之和、字母异位词分组、最长连续序列、移动零、盛最多水的容器

两数之和

class Solution {public int[] twoSum(int[] nums, int target) {int n = nums.length;  // 获取数组 nums 的长度// 外层循环：遍历数组中的每一个元素 nums[i]for(int i = 0; i < n; i++) {// 内层循环：从 nums[i] 的下一个元素 nums[j] 开始遍历// 这样避免了重复检查已经比较过的元素for(int j = i + 1; j < n; j++) {// 如果 nums[i] + nums[j] 的和等于目标值 targetif(nums[i] + nums[j] == target) {// 找到符合条件的两个数，返回它们的下标return new int[]{i, j};}}}// 如果没有找到符合条件的两个数，返回一个空数组return new int[0];}
}

字母异位词分组

• 字母排序法：

  • 字母异位词在排序后会得到相同的字符串。例如，“eat”和“tea”排序后都变成“aet”。
  • 基于这个特性，可以将字符串按照字母排序后的结果作为“键”存入一个哈希表（Map）。所有字母异位词会具有相同的“键”，因此它们可以归为一组。

• 哈希表（Map）存储：

  • 遍历输入的字符串数组，对于每一个字符串，排序得到一个新的字符串，作为哈希表的键。
  • 将该字符串加入对应的键值列表中（即字母异位词的分组）。

• 返回结果：

  • 最后，返回哈希表中所有的值（即分组后的字母异位词列表）。

// 字母异位词是由相同的字母组成，只是字母的顺序不同。
class Solution {public List<List<String>> groupAnagrams(String[] strs) {// 创建一个哈希表来存储异位词的分组Map<String, List<String>> map = new HashMap<>();// 遍历字符串数组for (String str : strs) {// 将每个字符串转为字符数组并排序char[] array = str.toCharArray();Arrays.sort(array);// 将排序后的字符数组转换成字符串作为哈希表的键String key = new String(array);// 获取该键对应的列表，如果没有则新建一个  // getOrDefault 是 Java 中 Map 接口的一个方法，用于从映射中获取指定键对应的值。如果键存在，则返回对应的值；如果键不存在，则返回一个默认值。List<String> list = map.getOrDefault(key, new ArrayList<>());// 将当前字符串添加到对应的列表中list.add(str);// 将更新后的列表重新放回哈希表map.put(key, list);}// 返回所有字母异位词的分组return new ArrayList<>(map.values());}
}

最长连续序列

具体步骤如下：

1. 将所有元素加入一个哈希集合 set，通过哈希集合可以在常数时间内查找某个元素是否存在。
2. 遍历数组中的每个元素，对于每个元素 x，判断 x-1 是否在哈希集合中。如果 x-1 存在，说明 x 不是连续序列的起始元素，可以跳过这个元素。
3. 如果 x-1 不存在，即 x 是一个连续序列的起始元素，则开始从 x 开始向后查找连续的数字，直到找不到连续的数字为止。
4. 在每次查找过程中，记录当前连续序列的长度，并更新最长的连续序列长度。

class Solution {public int longestConsecutive(int[] nums) {// 创建一个 HashSet 来存储数组中的元素HashSet<Integer> set = new HashSet<>();for (int num : nums) {set.add(num);}int longestStreak = 0;// 遍历数组中的每个元素for (int num : nums) {// 如果 num-1 不在 set 中，说明 num 是一个连续序列的起始元素if (!set.contains(num - 1)) {int currentNum = num;int currentStreak = 1;// 从当前元素开始，检查连续的元素while (set.contains(currentNum + 1)) {currentNum += 1;currentStreak += 1;set.remove(currentNum);  // 将已经访问的数字移除，避免重复计算}// 更新最长连续序列的长度longestStreak = Math.max(longestStreak, currentStreak);}}return longestStreak;}
}

移动零

思路：

1. 双指针法：

   • 使用两个指针 left 和 right。
   • right 用来遍历整个数组，逐个检查每个元素。
   • left 用来指示下一个应该放置非零元素的位置。

2. 遍历数组：

   • 如果 right 指向的元素是非零元素，我们就将其与 left 指向的元素交换，确保非零元素向数组的前面靠近。
   • 每次交换后，left 增加，指向下一个可以放置非零元素的位置。
   • right 不停地向后移动，直到遍历完整个数组。

3. 交换的目的：

   • 交换后，left 指向的地方总是非零元素，而 right 指向的元素经过交换后会被移动到适当的位置（如果是零，就会被移到后面）。

4. 保持顺序：

   • 非零元素的相对顺序会被保持，因为我们只做交换而没有改变原有元素的位置。

class Solution {public void moveZeroes(int[] nums) {int n = nums.length;int left = 0, right = 0;while (right < n) {  // 遍历数组if (nums[right] != 0) {  // 如果遇到非零元素swap(nums, left, right);  // 交换元素left++;  // 移动left指针，指向下一个可放置非零元素的位置}right++;  // 移动right指针，继续遍历}}public void swap(int[] nums, int left, int right) {int temp = nums[left];nums[left] = nums[right];nums[right] = temp;  // 交换left和right指向的元素}
}

盛最多水的容器

双指针策略：

• 初始化两个指针，l 和 r，分别指向数组的左右两端。
• 计算当前 l 和 r 指向的两条线形成的容器的面积：
  • 容器的面积 = min(height[l], height[r]) * (r - l)
  • height[l] 和 height[r] 代表了容器的高度，r - l 是容器的宽度。
• 然后更新最大面积 ans。
• 为了尝试增大水量，我们应该尽量移除较短的线，因为移除短的线有可能让我们找到更高的线，从而可能增大容器的水量。
• 移动指针：
  • 如果 height[l] 小于 height[r]，说明 l 对应的线较短，应该尝试向右移动 l。
  • 如果 height[l] 大于或等于 height[r]，说明 r 对应的线较短，应该尝试向左移动 r。

重复以上步骤，直到左右指针相遇。

class Solution {public int maxArea(int[] height) {int l = 0, r = height.length - 1;  // 初始化两个指针，分别指向数组的两端int ans = 0;  // 存储最大水量while (l < r) {  // 当左右指针没有相遇时int area = Math.min(height[l], height[r]) * (r - l);  // 计算当前容器的面积ans = Math.max(ans, area);  // 更新最大水量if (height[l] <= height[r]) {  // 如果左边的线较短，移动左指针l++;} else {  // 否则移动右指针r--;}}return ans;  // 返回最大水量}
}