LeetCode hot 100 (8-11,自用2026.04.03)

LeetCode hot 100 (8-11)3. 无重复字符的最长子串给定一个字符串s请你找出其中不含有重复字符的最长 子串的长度。示例 1:输入: s abcabcbb 输出: 3 解释: 因为无重复字符的最长子串是 abc所以其长度为 3。注意 bca 和 cab 也是正确答案。s由英文字母、数字、符号和空格组成思路一般出现散列表都是字符作为键出现的次数作为值涉及子串考虑滑动窗口要记录下标然后遇到同样的字符的时候往右划窗口刚好不包含那个重复的元素//外层循环扩展右边界内层循环扩展左边界for(intl0,r0;rn;r){//当前考虑的元素while(lrcheck()){//区间[left,right]不符合题意//扩展左边界}//区间[left,right]符合题意统计相关信息}题解classSolution{publicintlengthOfLongestSubstring(Strings){char[]sss.toCharArray();SetCharactersetnewHashSet();intres0;intns.length();for(intl0,r0;rn;r){charchss[r];while(set.contains(ch)){set.remove(ss[l]);l;}set.add(ss[r]);resMath.max(res,r-l1);}returnres;}}438. 找到字符串中所有字母异位词给定两个字符串s和p找到s中所有p的异位词的子串返回这些子串的起始索引。不考虑答案输出的顺序。示例 1:输入: s cbaebabacd, p abc 输出: [0,6] 解释: 起始索引等于 0 的子串是 cba, 它是 abc 的异位词。 起始索引等于 6 的子串是 bac, 它是 abc 的异位词。思路p的长度肯定是s子串的长度子串的顺序固定了的话那就从头扫到尾因为只包含小写字母维护两个26大小的数组就行补充出现次数也要一致是定长滑动窗口只需要计数统计两个数组相同是Arrays.equals(数组1数组2)题解classSolution{publicListIntegerfindAnagrams(Strings,Stringp){intsLens.length(),pLenp.length();if(sLenpLen){returnnewArrayListInteger();}ListIntegerresnewArrayList();int[]sCountnewint[26];int[]pCountnewint[26];for(inti0;ipLen;i){sCount[s.charAt(i)-a];pCount[p.charAt(i)-a];}if(Arrays.equals(sCount,pCount)){res.add(0);}for(inti0;isLen-pLen;i){--sCount[s.charAt(i)-a];sCount[s.charAt(ipLen)-a];if(Arrays.equals(sCount,pCount)){res.add(i1);}}returnres;}}优化思路Arrays.equals(sCount,pCount)在比较两个数组 优化之后只用一个数组 count[x] 当前窗口中字符x的个数 - p中字符x的个数 differ 有多少个字符的 count[x] ! 0 也就是differ 0时就是异位词 这样每次窗口移动只需要关心 出去的那个字符 进来的那个字符classSolution{publicListIntegerfindAnagrams(Strings,Stringp){intsLens.length(),pLenp.length();if(sLenpLen){returnnewArrayListInteger();}ListIntegeransnewArrayListInteger();int[]countnewint[26];for(inti0;ipLen;i){count[s.charAt(i)-a];--count[p.charAt(i)-a];}intdiffer0;for(intj0;j26;j){if(count[j]!0){differ;}}if(differ0){ans.add(0);}for(inti0;isLen-pLen;i){if(count[s.charAt(i)-a]1){// 窗口中字母 s[i] 的数量与字符串 p 中的数量从不同变得相同--differ;}elseif(count[s.charAt(i)-a]0){// 窗口中字母 s[i] 的数量与字符串 p 中的数量从相同变得不同differ;}--count[s.charAt(i)-a];if(count[s.charAt(ipLen)-a]-1){// 窗口中字母 s[ipLen] 的数量与字符串 p 中的数量从不同变得相同--differ;}elseif(count[s.charAt(ipLen)-a]0){// 窗口中字母 s[ipLen] 的数量与字符串 p 中的数量从相同变得不同differ;}count[s.charAt(ipLen)-a];if(differ0){ans.add(i1);}}returnans;}}560. 和为 K 的子数组给你一个整数数组nums和一个整数k请你统计并返回 该数组中和为k的子数组的个数 。子数组是数组中元素的连续非空序列。示例 1输入nums [1,1,1], k 2 输出2思路排序然后左右同时扫大了的话就左移动小了的话就右移动 判断左是否比总和大如果大就结束判断右是否比总和小小的话也结束 这是两个元素的三个元素呢…… 上面的思路有问题不能排序没有单调的话双指针也失效了标准做法是前缀和 哈希表题解classSolution{publicintsubarraySum(int[]nums,intk){MapInteger,IntegermapnewHashMap();map.put(0,1);// 前缀和为0出现1次intsum0;intans0;for(intnum:nums){sumnum;if(map.containsKey(sum-k)){ansmap.get(sum-k);}map.put(sum,map.getOrDefault(sum,0)1);}returnans;}}239. 滑动窗口最大值给你一个整数数组nums有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的k个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。示例 1输入nums [1,3,-1,-3,5,3,6,7], k 3 输出[3,3,5,5,6,7] 解释 滑动窗口的位置 最大值 --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7思路定长滑动窗口最差的情况就是左右指针for然后比较里面的内容单调队列题解classSolution{publicint[]maxSlidingWindow(int[]nums,intk){// 数组长度intnnums.length;// 定义单调队列队列里存储的是索引。DequeIntegerdequenewLinkedList();// 初始化窗口也就是完整导入前k个数字for(inti0;ik;i){// 队列为不空且新的数字比队列末尾数字大的时候while(!deque.isEmpty()nums[i]nums[deque.peekLast()]){// 弹出末尾元素deque.pollLast();}// 从队尾加新元素上去deque.offerLast(i);}// 定义最后返回数组大小是n-k1int[]ansnewint[n-k1];// 第一个元素是队头的元素ans[0]nums[deque.peekFirst()];// 从位置k开始滑动直到小于nfor(intik;in;i){// 队列不空且新的数字比队尾大while(!deque.isEmpty()nums[i]nums[deque.peekLast()]){// 从队尾弹出deque.pollLast();}// 从队尾加入新元素deque.offerLast(i);// 判断队头还在不在窗口内不在的话就从前面弹出while(deque.peekFirst()i-k){deque.pollFirst();}// 存入当前窗口最大值索引是deque.peekFirst也就是队头元素ans[i-k1]nums[deque.peekFirst()];}returnans;}}