209，3，904，76，438，560，239
套路：
初始化左指针，初始化右指针，初始化窗口，初始化结果
右指针遍历扩大窗口
进行窗口判断
左指针遍历缩小窗口
最大值在扩窗时收集结果，最小值在缩窗时收集结果
template
import java.util.HashMap;
public class SlidingWindow {
public void slidingWindow(String s, String t) {
HashMap<Character, Integer> need = new HashMap<>();
HashMap<Character, Integer> window = new HashMap<>();
for (char c : t.toCharArray()) {
need.put(c, need.getOrDefault(c, 0) + 1);
}
int left = 0, right = 0;
int valid = 0;
while (right < s.length()) {
// c 是将移入窗口的字符
char c = s.charAt(right);
// 右移窗口
right++;
// 进行窗口内数据的一系列更新
// 例如：更新窗口内字符的计数
window.put(c, window.getOrDefault(c, 0) + 1);
// 当窗口内满足某些条件时进行调试输出
System.out.println("window: [" + left + ", " + right + ")");
// 判断左侧窗口是否要收缩
while (window needs shrink) { // 这里的条件需要根据具体问题来定义
// d 是将移出窗口的字符
char d = s.charAt(left);
// 左移窗口
left++;
// 进行窗口内数据的一系列更新
// 例如：减少窗口内字符的计数
window.put(d, window.getOrDefault(d, 1) - 1);
}
}
}
public static void main(String[] args) {
SlidingWindow sw = new SlidingWindow();
sw.slidingWindow("your_string_s", "your_string_t");
}
}
209. Minimum Size Subarray Sum
Medium
Given an array of positive integers nums and a positive integer target, return the minimal length of a
subarray
whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.
Example 1:
Input: target = 7, nums = [2,3,1,2,4,3] Output: 2 Explanation: The subarray [4,3] has the minimal length under the problem constraint.
class Solution {
// 方法：求最短的子数组，其和至少为 target
public int minSubArrayLen(int target, int[] nums) {
int left = 0; // 左指针，用于标记子数组的开始位置
int sum = 0; // 用于记录当前子数组的和
int ans = nums.length + 1; // 初始化答案为一个不可能的大值（数组长度+1）
// 遍历数组，右指针 right 表示子数组的结束位置
for (int right = 0; right < nums.length; right++) {
sum += nums[right]; // 向当前子数组的和中加入 nums[right]
// 当当前子数组的和大于等于目标值时，尝试缩小子数组
while (sum >= target) {
sum -= nums[left]; // 从和中去掉子数组的第一个元素
ans = Math.min(ans, right - left + 1); // 更新最小子数组长度
left++; // 左指针向右移动，减小子数组的长度
}
}
// 检查是否找到了符合条件的子数组
if (ans == nums.length + 1) {
return 0; // 如果 ans 仍然是初始化的值，说明没有找到符合条件的子数组，返回 0
} else {
return ans; // 否则返回找到的最短子数组长度
}
}
}
3. Longest Substring Without Repeating Characters
Medium
Given a string s, find the length of the longest substring without repeating characters.
Example 1:
Input: s = "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3.
class Solution {
public int lengthOfLongestSubstring(String s) {
Set<Character> set = new HashSet<>(); // 使用一个HashSet来记录每个字符是否出现过
char[] ch = s.toCharArray(); // 将输入的字符串转换为字符数组，便于索引操作
int left = 0; // 左指针，用于表示当前考察的子串的开始位置
int count = 0; // 当前窗口的长度
int ans = 0; // 用于记录遇到的最长无重复字符子串的长度
// 遍历字符串中的每个字符
for (int right = 0; right < ch.length; right++) {
if (!set.contains(ch[right])) { // 如果当前字符不在HashSet中，说明未重复
set.add(ch[right]); // 将此字符加入HashSet
count = count + 1; // 窗口长度增加
ans = Math.max(ans, count); // 更新最大长度
} else { // 如果当前字符已在HashSet中，说明重复了
// 移动左指针，直到移除重复的字符
while (set.contains(ch[right])) {
set.remove(ch[left]); // 移除左指针处的字符
left++; // 左指针向右移动
count--; // 窗口长度减少
}
set.add(ch[right]); // 将当前字符加入HashSet
count++; // 窗口长度增加
}
}
return ans; // 返回最长无重复字符子串的长度
}
}
class Solution {
public int lengthOfLongestSubstring(String s) {
int[] ch = new int[128];
for(int i=0;i<128;i++){
ch[i]=-1;
}
int ans=0;
int st=0;
for(int i=0;i<s.length();i++){
int c = s.charAt(i);
if(ch[c]!=-1){
st=Math.max(st,ch[c]);
}
ans=Math.max(ans,i-st+1);
ch[c]=i+1;
}
return ans;
}
}904. Fruit Into Baskets
Medium
You are visiting a farm that has a single row of fruit trees arranged from left to right. The trees are represented by an integer array fruits where fruits[i] is the type of fruit the ith tree produces.
You want to collect as much fruit as possible. However, the owner has some strict rules that you must follow:
- You only have two baskets, and each basket can only hold a single type of fruit. There is no limit on the amount of fruit each basket can hold.
- Starting from any tree of your choice, you must pick exactly one fruit from every tree (including the start tree) while moving to the right. The picked fruits must fit in one of your baskets.
- Once you reach a tree with fruit that cannot fit in your baskets, you must stop.
Given the integer array fruits, return the maximum number of fruits you can pick.
Example 1:
Input: fruits = [1,2,1] Output: 3 Explanation: We can pick from all 3 trees.
class Solution {
public int totalFruit(int[] fruits) {
int left = 0; // 初始化左指针，表示当前子数组的开始位置
int right = 0; // 初始化右指针，表示当前子数组的结束位置
int resault = 0; // 用于存储最长子数组的长度
Map<Integer,Integer> map = new HashMap<>(); // 哈希表用于存储窗口内各种水果的数量
// 遍历所有水果
for(right = 0; right < fruits.length; right++){
// 将当前水果加入到哈希表中，计数加1
map.put(fruits[right] , map.getOrDefault(fruits[right] , 0) + 1);
// 当哈希表中的水果种类超过2种时，缩小窗口
while(map.size() > 2){
// 将左指针所在的水果计数减1
map.put(fruits[left], map.get(fruits[left]) - 1);
// 如果某种水果的数量减到0，从哈希表中移除
if(map.get(fruits[left]) == 0){
map.remove(fruits[left]);
}
// 左指针向右移动，缩小窗口
left++;
}
// 更新最大子数组的长度
resault = Math.max(resault, right - left + 1);
}
return resault; // 返回最大长度
}
}
76. Minimum Window Substring
Hard
Given two strings s and t of lengths m and n respectively, return the minimum window
substring
of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".
The testcases will be generated such that the answer is unique.
Example 1:
Input: s = "ADOBECODEBANC", t = "ABC" Output: "BANC" Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.
class Solution {
public String minWindow(String s, String t) {
// 边界条件检查
if (s == null || t == null || s.length() == 0 || t.length() == 0 || s.length() < t.length()) {
return ""; // 如果输入不合理，则返回空字符串
}
int[] map = new int[128]; // ASCII字符映射表，用于记录字符串t中各字符的数量
int count = t.length(); // 需要匹配的字符总数
int start = 0, end = 0; // 滑动窗口的起始和结束位置
int minLen = Integer.MAX_VALUE; // 最小窗口长度，初始化为最大整数值
int startIndex = 0; // 最小窗口的起始索引
// 遍历字符串t，初始化字符计数器
for (char c : t.toCharArray()) {
map[c]++; // 增加t中字符的计数
}
char[] chS = s.toCharArray(); // 将字符串s转换为字符数组，以便操作
// 扩展窗口的右边界
while (end < chS.length) {
// 当前字符在t中，减少相应的计数，并扩展窗口的右边界
if (map[chS[end++]]-- > 0) {
count--; // 减少需要匹配的字符计数
}
// 当所有字符都匹配后
while (count == 0) {
// 如果当前窗口的长度小于已记录的最小长度，则更新最小窗口
if (end - start < minLen) {
startIndex = start; // 更新最小窗口起始索引
minLen = end - start; // 更新最小窗口长度
}
// 尝试收缩窗口的左边界，同时更新字符计数器和匹配计数
if (map[chS[start++]]++ == 0) {
count++; // 如果移除的字符是需要的字符，则增加需要匹配的字符计数
}
}
}
// 如果没有找到有效的窗口，则返回空字符串，否则返回最小窗口子字符串
return minLen == Integer.MAX_VALUE ? "" : new String(chS, startIndex, minLen);
}
}
438. Find All Anagrams in a String
Solved
Medium
Topics
Companies
Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
Example 1:
Input: s = "cbaebabacd", p = "abc" Output: [0,6] Explanation: The substring with start index = 0 is "cba", which is an anagram of "abc". The substring with start index = 6 is "bac", which is an anagram of "abc".
class Solution {
public List<Integer> findAnagrams(String s, String p) {
int sLen = s.length(), pLen = p.length(); // s和p的长度
if (sLen < pLen) {
return new ArrayList<Integer>(); // 如果s的长度小于p的长度，直接返回空列表
}
List<Integer> ans = new ArrayList<Integer>(); // 存储所有异位词起始索引的列表
int[] sCount = new int[26]; // s中的字符计数
int[] pCount = new int[26]; // p中的字符计数
// 初始化计数数组
for (int i = 0; i < pLen; ++i) {
++sCount[s.charAt(i) - 'a']; // 对s的前pLen个字符进行计数
++pCount[p.charAt(i) - 'a']; // 对p的所有字符进行计数
}
// 如果初始化时s的前pLen个字符的计数与p的字符计数相同，说明找到一个异位词
if (Arrays.equals(sCount, pCount)) {
ans.add(0); // 将起始索引0添加到结果列表中
}
// 遍历s中的每个字符，使用滑动窗口更新字符计数
for (int i = 0; i < sLen - pLen; ++i) {
--sCount[s.charAt(i) - 'a']; // 移除窗口最左侧的字符计数
++sCount[s.charAt(i + pLen) - 'a']; // 添加窗口最右侧的新字符计数
// 比较更新后的s计数和p计数是否相同，相同则为异位词
if (Arrays.equals(sCount, pCount)) {
ans.add(i + 1); // 将当前异位词的起始索引添加到结果列表中
}
}
return ans; // 返回包含所有异位词起始索引的列表
}
}
560. Subarray Sum Equals K
Medium
Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.
A subarray is a contiguous non-empty sequence of elements within an array.
Example 1:
Input: nums = [1,1,1], k = 2 Output: 2
public class Solution {
public int subarraySum(int[] nums, int k) {
int count = 0; // 用于计算和为k的子数组数量
int pre = 0; // 用于累加前缀和
HashMap<Integer, Integer> mp = new HashMap<>(); // 哈希表用来存储前缀和及其出现的次数
mp.put(0, 1); // 初始化，对于前缀和为0的情况，假设已经出现一次（处理边界情况，如数组的部分元素和正好为k）
for (int i = 0; i < nums.length; i++) {
pre += nums[i]; // 累加当前元素到前缀和中
// 如果当前前缀和减去k的结果已存在于哈希表中，说明存在一个子数组的和为k
if (mp.containsKey(pre - k)) {
count += mp.get(pre - k); // 将这些子数组的数量加到count上
}
// 更新当前前缀和的计数，如果这个前缀和第一次出现，则初始化为1，否则累加
mp.put(pre, mp.getOrDefault(pre, 0) + 1);
}
return count; // 返回所有满足条件的子数组数量
}
}
239. Sliding Window Maximum
Hard
You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.
Return the max sliding window.
Example 1:
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3 Output: [3,3,5,5,6,7] Explanation: Window position Max --------------- ----- [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
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int len = nums.length; // 数组的长度
int[] res = new int[len - k + 1]; // 存储每个窗口的最大值
int left = 0; // 窗口的左边界
int right = k - 1; // 窗口的右边界
int max = Integer.MIN_VALUE; // 当前窗口中的最大值
int maxIndex = -1; // 当前最大值的索引
// 遍历数组，直到右边界达到数组的末尾
while (right < len) {
// 如果最大值的索引仍在窗口内
if (left <= maxIndex) {
// 检查新加入窗口的元素是否大于当前最大值
if (nums[right] >= nums[maxIndex]) {
maxIndex = right; // 更新最大值索引
max = nums[right]; // 更新最大值
}
// 否则，重新计算当前窗口的最大值
} else if (nums[right] >= max - 1 ) {
maxIndex = right;
max = nums[right];
} else if (nums[left] >= max - 1 ) {
maxIndex = left;
max = nums[left];
} else {
max = nums[left];
// 遍历当前窗口，找出最大值和对应的索引
for (int j = left + 1; j <= right; j++) {
if (nums[j] >= max) {
maxIndex = j;
max = nums[j];
}
}
}
// 将当前窗口的最大值存入结果数组
res[left] = max;
// 窗口向右移动
left++;
right++;
}
return res; // 返回结果数组
}
}
