【二刷hot-100】day2

server/2024/10/18 5:32:10/

1.无重复字符的最长子串

2.找到字符串中所有字母异位词

3.和为 K 的子数组

4.滑动窗口最大值

1.无重复字符的最长子串

java">class Solution {public int lengthOfLongestSubstring(String s) {Map<Character,Integer> dict =new HashMap<>();int ret=0;int i=-1;for(int j=0;j<s.length();j++){char c=s.charAt(j);//如果字符在字典存在if(dict.containsKey(c)){//确保左指针不会向左移动//更新左指针为当前字符索引和当前左指针的最大值i=Math.max(dict.get(c),i);}//当前字符和索引存入字典dict.put(c,j);ret=Math.max(ret,j-i);}return ret;}
}

2.找到字符串中所有字母异位词

经典思路：

（s中统计p字符串每个字符的出现次数）

java">        //s中找p中每个字符的出现次数Map<Character,Integer> counter1=new HashMap<>();for(char c:p.toCharArray()){counter1.put(c,counter1.getOrDefault(c,0)+1);}

java">class Solution {public List<Integer> findAnagrams(String s, String p) {List<Integer> ans = new ArrayList<>();// 初始化一个数组来统计字符串 p 中每个字符的出现次数int[] cnt = new int[26];for(int i = 0; i < p.length(); i++){cnt[p.charAt(i) - 'a']++;}// l 和 r 分别表示滑动窗口的左右边界int l = 0;for(int r = 0; r < s.length(); r++){// 更新当前窗口中字符的计数数组cnt[s.charAt(r) - 'a']--;// 从左侧收缩窗口，直到当前字符的计数在限定范围内while(cnt[s.charAt(r) - 'a'] < 0){cnt[s.charAt(l) - 'a']++;l++;}// 检查当前窗口大小是否等于字符串 p 的大小if(r - l + 1 == p.length()){ans.add(l);}}return ans;}
}

3.和为 K 的子数组

java">class Solution {public int subarraySum(int[] nums, int k) {int ret=0;int s=0;HashMap<Integer,Integer> dict=new HashMap<>();//数组-1的位置前缀和应该是1dict.put(0,1);for(int x:nums){s+=x;//如果存在s-k的子数组，加上数量ret+=dict.getOrDefault(s-k,0);dict.put(s,dict.getOrDefault(s,0)+1);}return ret;}
}

4.滑动窗口最大值

java">import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;class Solution {public int[] maxSlidingWindow(int[] nums, int k) {// 创建双端队列Deque<Integer> deque = new LinkedList<>();List<Integer> ret = new ArrayList<>();int n = nums.length;for (int i = 0; i < n; i++) {// 如果双端队列不为空且当前元素的索引与队首元素的索引之差大于等于窗口大小 k，移除队首元素while (!deque.isEmpty() && i - deque.peekFirst() >= k) {deque.pollFirst();}// 保持双端队列递减while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {deque.pollLast();}deque.addLast(i);// 当窗口大小达到 k 时，开始记录窗口最大值if (i >= k - 1) {ret.add(nums[deque.peekFirst()]);}}// 将 List<Integer> 转换为 int[]int[] finalResult = new int[ret.size()];for (int i = 0; i < ret.size(); i++) {finalResult[i] = ret.get(i);}return finalResult;}
}

顶不了了，好多java语法不会，呜呜呜。