LeetCode算法日记 - Day 5: 长度最小的子数组、无重复字符的最长子串
目录
1. 长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例 1：
输入：target = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：
输入：target = 4, nums = [1,4,4] 输出：1
示例 3：
输入：target = 11, nums = [1,1,1,1,1,1,1,1] 输出：0
1.1 题目解析
针对一段连续区间，寻找最小长度的子数组，使其元素和大于等于给定目标值（通常称为“最小子数组和”问题），利用正数相加和只能增加的单调性，使用滑动窗口方法解决。此利用单调性避免没有必要的枚举行为。虽然有两层循环，但是时间复杂度为O(N)。
1.2 解法
滑动窗口的核心是使用两个指针（左指针和右指针）动态调整窗口范围：
- 窗口定义：窗口代表子数组，其和记为 sum。
- 目标：找到最小长度 {min_len}
- 关键思想：
- 移动 right 扩大窗口，增加 sum，直到 sum>=target。
- 然后移动 缩小窗口，减少 sum，同时检查是否仍满足 sum>=target (因为移除小元素可能保留满足条件的更小子数组)。
- 更新 min_len 为当前窗口长度 right-left+1 的最小值。
- 为什么高效：每个元素最多被添加和移除一次，确保线性时间复杂度
以下是滑动窗口算法的具体步骤
i）初始化指针：左右指针定义从0下标开始
ii）移动右指针：将 right 位置的元素加入窗口，直到 sum>=target
iii）缩小窗口并检查：将 left 位置的元素移动出窗口，并且检查是否 sum>= target
iiii）循环 ii, iii 直到 right>=n
1.3 代码实现
class Solution { public int minSubArrayLen(int target, int[] nums) { int min_len=Integer.MAX_VALUE,n=nums.length,sum =0; for(int left =0,right=0;right<n;right++){ sum += nums[right]; while(sum >= target){ int length = right-left+1; min_len = Math.min(min_len,length); sum-=nums[left++]; } } return min_len == Integer.MAX_VALUE ?0:min_len; } }2. 无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。
示例 1:
输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串
2.1 题目解析
本题目可以使用滑动窗口来解决，当窗口里未包含字符时增大窗口，并且记录新的最长子字符串值，当遇到已经包含的字符时，通过 while 循环直接跳过重复的元素。
i）可以看得出当窗口没有重复元素删除时，字符串长度始终是不会增加的。
ii）我们可以直接通过 while 循环快速移动并且删除重复的元素。
iii）while 循环之后再记录当前字符串长度，切记不能在 while 循环时记录长度，会陷入只有在删除重复元素时才会更新长度。
2.2 解法
i）定义变量
ii）统计 right 所指元素的数量
iii）进行判断，如果重复则通过移动 left 和 while 循环跳过重复元素
iiii）记录长度
2.3 代码实现
class Solution { public int lengthOfLongestSubstring(String ss) { int n = ss.length(),ret = 0; int[] hash = new int[128]; char[] s = ss.toCharArray(); for(int left = 0,right =0;right<n;right++){ hash[s[right]]++; while(hash[s[right]]>1){ hash[s[left++]]--; } ret = Math.max(ret,right-left+1); } return ret; } }
