leetcode
3. 无重复字符的最长子串【中等】
学习：leetcode题解
题目链接：3. 无重复字符的最长子串
题目内容：
速记：抓住重点最长、子串，则表名我们要找到连续且无重复的，这时候我们就可以使用滑动窗口来进行解决。
①set版本，使用集合开销较大。
②数组版本，限定在0-128之间，开销相对于set小。
思路：
1、滑动窗口（set方式）
思路：题目要求是最长子串，那么一定是连续的子串。这里要是想要时间复杂度为O(n)就需要使用到滑动窗口，规则如下： 这里我直接拿leetcode官方的示例： 以(a)bcabcbb开始的最长字符串为(abc)abcbb; 以a(b)cabcbb开始的最长字符串为a(bca)bcbb; 以ab(c)abcbb开始的最长字符串为ab(cab)cbb; 以abc(a)bcbb开始的最长字符串为abc(abc)bb; 以abca(b)cbb开始的最长字符串为abca(bc)bb; 以abcab(c)bb开始的最长字符串为abcab(cb)b; 以abcabc(b)b开始的最长字符串为abcabc(b)b; 以abcabcb(b)开始的最长字符串为abcabcb(b)。 思路：每个区间我们可以使用set来进行暂存，每进行移动窗口，将左边的一位进行移除，窗口中的依旧在set集合里不动，之后再去依次添加之后没出现过的元素。
复杂度分析：时间复杂度O(n)，空间复杂度O(∣Σ∣)：O(∣Σ∣)指的是字符集的大小，也就是默认为ASCII 码[0,128) 内的字符，默认128个，这里题目指的是数字、字母、空格。
public int lengthOfLongestSubstring(String s) { //哈希 Set<Character> sets = new HashSet<>(); //右边指针 int right = -1; int maxLen = 0; //优化点：进行剪枝 for (int i = 0; i < s.length() - maxLen; i++) { //滑动窗口右移，移除左边一个元素 if (i != 0) { sets.remove(s.charAt(i - 1)); } //若是在指定范围内&添加成功 while (right + 1 < s.length() && sets.add(s.charAt(right + 1))){ right++; } maxLen = Math.max(right - i + 1, maxLen); } return maxLen; }
2、滑动窗口（数组）
思路：题目给定范围那么ASCII码的数字表示即为[0-128]之间，1表示在滑动窗口中的了，0表示还未添加。
代码：时间复杂度O(n)，空间复杂度O(∣Σ∣)
public int lengthOfLongestSubstring(String s) { //哈希 int[] chars = new int[128]; //右边指针 int right = -1; int maxLen = 0; //优化点：进行剪枝 for (int i = 0; i < s.length() - maxLen; i++) { //滑动窗口右移，移除左边一个元素 if (i != 0) { chars[s.charAt(i - 1)] = 0; } //若是在指定范围内&添加成功 while (right + 1 < s.length() && chars[s.charAt(right + 1)] == 0){ chars[s.charAt(right + 1)] = 1; right++; } maxLen = Math.max(right - i + 1, maxLen); } return maxLen; }
滑动窗口的最大值【困难】
题目链接：滑动窗口的最大值
题目内容：给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
思路1：双端队列来进行。【推荐】
时间复杂度：O(n)，数组长度为n，只遍历一遍数组。 空间复杂度：O(m)，窗口长度m，双向队列最长时，将窗口填满。 class Solution { public int[] maxSlidingWindow(int[] nums, int k) { if (nums.length < k || nums.length == 0) { return new int[0]; } int[] res = new int[nums.length - k + 1]; int j = 0; //采用双端队列来解决 ArrayDeque<Integer> deque = new ArrayDeque<>(); //1、第一个窗口 for (int i = 0; i < k; i++) { while (!deque.isEmpty() && nums[i] > deque.peekLast()) { deque.pollLast(); } deque.addLast(nums[i]); } res[j++] = deque.peekFirst(); //2、之后的窗口 for (int i = k; i < nums.length; i++) { if (!deque.isEmpty() && deque.peekFirst() == nums[i - k]) { deque.pollFirst(); } while (!deque.isEmpty() && nums[i] > deque.peekLast()) { deque.pollLast(); } deque.addLast(nums[i]); res[j++] = deque.peekFirst(); } return res; } }
