【LeetCode 随笔】面试经典 150 题【中等＋困难】持续更新中。。。

🌈你好呀！我是 山顶风景独好
💝欢迎来到我的博客，很高兴能够在这里和您见面！
💝希望您在这里可以感受到一份轻松愉快的氛围！
💝不仅可以获得有趣的内容和知识，也可以畅所欲言、分享您的想法和见解。
🚀 欢迎一起踏上探险之旅，挖掘无限可能，共同成长！

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。

解题思路：

• 若向内 移动短板 ，水槽的短板 min(h[i],h[j])min(h[i], h[j])min(h[i],h[j]) 可能变大，因此下个水槽的面积 可能增大 。
• 若向内 移动长板 ，水槽的短板 min(h[i],h[j])min(h[i], h[j])min(h[i],h[j])​ 不变或变小，因此下个水槽的面积 一定变小 。

因此，初始化双指针分列水槽左右两端，循环每轮将短板向内移动一格，并更新面积最大值，直到两指针相遇时跳出；即可获得最大面积。

class Solution {  public int maxArea(int[] height) {  // 初始化两个指针i和j，分别指向数组的第一个和最后一个元素  int i = 0, j = height.length - 1, res = 0;  // 当i小于j时，继续循环  while(i < j) {  // 计算当前i和j所构成的矩形的面积  // 面积由较短的那条边和两条边之间的距离决定  // 如果左边的边更短，则更新最大面积并向右移动左边的指针  // 否则，更新最大面积并向左移动右边的指针  res = height[i] < height[j] ?   Math.max(res, (j - i) * height[i++]):   Math.max(res, (j - i) * height[j--]);   }  // 循环结束后，res保存了能盛放的最大水量  return res;  }  
}

15.【中等】三数之和

• 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
• 你返回所有和为 0 且不重复的三元组。
• 注意：答案中不可以包含重复的三元组。

示例 ：

• 输入：nums = [-1,0,1,2,-1,-4]
• 输出：[[-1,-1,2],[-1,0,1]]
• 解释：
  nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
  nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
  nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
  不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
  注意，输出的顺序和三元组的顺序并不重要。

class Solution {  public List<List<Integer>> threeSum(int[] nums) {  // 将数组进行排序，排序有助于减少后续循环的复杂性  Arrays.sort(nums);  // 创建一个二维列表，用于保存结果  List<List<Integer>> res = new ArrayList<>();  // 遍历数组，k作为三元组的第一个数  for(int k = 0; k < nums.length - 2; k++){  // 如果第一个数已经大于0，那么后面的数组合起来一定大于0，直接跳出循环  if(nums[k] > 0) break;  // 跳过重复的元素，避免产生重复的三元组  if(k > 0 && nums[k] == nums[k - 1]) continue;  // 定义双指针i和j，分别指向k的下一个元素和数组的最后一个元素  int i = k + 1, j = nums.length - 1;  // 当i < j时，继续循环  while(i < j){  // 计算当前i、j和k三个数的和  int sum = nums[k] + nums[i] + nums[j];  // 如果和小于0，说明需要增加和的值，移动左指针i  if(sum < 0){  // 跳过重复的元素  while(i < j && nums[i] == nums[++i]);  }   // 如果和大于0，说明需要减少和的值，移动右指针j  else if (sum > 0) {  // 跳过重复的元素  while(i < j && nums[j] == nums[--j]);  }   // 如果和等于0，找到了一个三元组，将其添加到结果列表中  else {  res.add(new ArrayList<Integer>(Arrays.asList(nums[k], nums[i], nums[j])));  // 跳过重复的元素，避免产生重复的三元组  while(i < j && nums[i] == nums[++i]);  while(i < j && nums[j] == nums[--j]);  }  }  }  // 返回结果列表  return res;  }  
}

209.【中等】长度最小的子数组

• 给定一个含有 n 个正整数的数组和一个正整数 target 。
• 找出该数组中满足其总和大于等于 target 的长度最小的 连续
  子数组
  [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 ：

• 输入：target = 7, nums = [2,3,1,2,4,3]
• 输出：2
• 解释：子数组 [4,3] 是该条件下的长度最小的子数组。

public int minSubArrayLen(int s, int[] nums) {  // 初始化左指针和右指针，都从数组的起始位置开始  int lo = 0, hi = 0;  // 初始化当前窗口的和为0  int sum = 0;  // 初始化最小子数组长度为Integer的最大值，用于后续比较和更新  int min = Integer.MAX_VALUE;  // 当右指针还没有超出数组范围时，继续循环  while (hi < nums.length) {  // 将当前右指针指向的元素加到和中  sum += nums[hi++];  // 当和已经大于等于s时，开始尝试缩小窗口  while (sum >= s) {  // 更新最小子数组长度（如果当前窗口长度更小的话）  min = Math.min(min, hi - lo);  // 尝试缩小窗口：从和中减去左指针指向的元素  sum -= nums[lo++];  }  }  // 如果min仍然是Integer的最大值，说明没有找到满足条件的子数组，返回0  // 否则，返回找到的最小子数组长度  return min == Integer.MAX_VALUE ? 0 : min;  
}

3.【中等】无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的最长
子串的长度。

示例 :

• 输入: s = “abcabcbb”
• 输出: 3
• 解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

class Solution {  public int lengthOfLongestSubstring(String s) {  // 创建一个HashMap用于存储字符和它们的最新索引  Map<Character, Integer> dic = new HashMap<>();  // 初始化左指针i为-1，表示还没有开始寻找无重复子串  int i = -1, res = 0, len = s.length();        // 遍历字符串s的每一个字符，j为右指针  for(int j = 0; j < len; j++) {  // 如果字符s.charAt(j)已经在dic中存在，则更新左指针i  // 使其为当前索引j和dic中存储的索引之间的较大值  // 这样做的目的是保证左指针i指向的是无重复子串的起始位置  if (dic.containsKey(s.charAt(j)))  i = Math.max(i, dic.get(s.charAt(j))); // 更新左指针 i               // 将字符s.charAt(j)和其索引j存入dic中  // 如果之前已经存在该字符，则更新其索引为最新的j  dic.put(s.charAt(j), j); // 哈希表记录                // 计算当前无重复子串的长度，并更新结果res  // res始终记录着遍历过程中找到的最长无重复子串的长度  res = Math.max(res, j - i); // 更新结果  }            // 返回最长无重复子串的长度  return res;  }  
}

30.【困难】串联所有单词的子串

• 给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。
• s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。
• 例如，如果 words = [“ab”,“cd”,“ef”]， 那么 “abcdef”， “abefcd”，“cdabef”， “cdefab”，“efabcd”， 和 “efcdab” 都是串联子串。 “acdbef” 不是串联子串，因为他不是任何 words 排列的连接。
• 返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。

示例 ：

• 输入：s = “barfoothefoobarman”, words = [“foo”,“bar”]
• 输出：[0,9]
• 解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。
  子串 “barfoo” 开始位置是 0。它是 words 中以 [“bar”,“foo”] 顺序排列的连接。
  子串 “foobar” 开始位置是 9。它是 words 中以 [“foo”,“bar”] 顺序排列的连接。
  输出顺序无关紧要。返回 [9,0] 也是可以的。

class Solution {  public List<Integer> findSubstring(String s, String[] words) {  // 存储所有符合条件的子串起始位置的列表  List<Integer> res = new ArrayList<Integer>();           // words数组的长度，即单词的数量  int m = words.length;  // 单个单词的长度  int n = words[0].length();  // 原始字符串s的长度  int ls = s.length();  // 遍历原始字符串s的每一个可能的起始位置，每个位置从0到n-1开始（因为单词长度为n）  for (int i = 0; i < n; i++) {  // 如果从当前位置开始，剩余长度不足以包含m个单词，则跳出循环  if (i + m * n > ls) {  break;  }  // 用于比较和统计的Map  Map<String, Integer> differ = new HashMap<String, Integer>();  // 初始化differ，将前m个单词加入Map，并统计每个单词出现的次数  for (int j = 0; j < m; j++) {  String word = s.substring(i + j * n, i + (j + 1) * n);  differ.put(word, differ.getOrDefault(word, 0) + 1);  }  // 接下来将words数组中的单词从differ中减去，看它们是否完全匹配  for (String word : words) {  differ.put(word, differ.getOrDefault(word, 0) - 1);  // 如果某个单词在differ中的计数变为0，则从Map中移除  if (differ.get(word) == 0) {  differ.remove(word);  }  }  // 接下来从起始位置i开始，每次移动n个位置，检查是否有符合条件的子串  for (int start = i; start < ls - m * n + 1; start += n) {  // 如果不是初始化的起始位置i，则需要更新differ  if (start != i) {  // 检查右边界的单词是否在differ中，如果在，则增加计数  String word = s.substring(start + (m - 1) * n, start + m * n);  differ.put(word, differ.getOrDefault(word, 0) + 1);  // 如果计数变为0，则从Map中移除  if (differ.get(word) == 0) {  differ.remove(word);  }  // 检查左边界的单词是否在differ中，如果在，则减少计数  word = s.substring(start - n, start);  differ.put(word, differ.getOrDefault(word, 0) - 1);  // 如果计数变为0，则从Map中移除  if (differ.get(word) == 0) {  differ.remove(word);  }  }  // 如果differ为空，说明找到了一个符合条件的子串，将其起始位置加入res  if (differ.isEmpty()) {  res.add(start);  }  }  }  // 返回所有符合条件的子串起始位置列表  return res;  }  
}