LeetCode热题100（简单/中等）—— 滑动窗口 + 子串

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。注意 "bca" 和 "cab" 也是正确答案。

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // 哈希集合，用来记录当前窗口内的字符
        Set<Character> set = new HashSet<>();
        
        int n = s.length();
        int a = 0; // 左指针
        int b = 0; // 右指针
        int maxLength = 0;

        while (b < n) {
            char currentChar = s.charAt(b);
            
            // 如果记事本里已经有了这个字符，说明重复了！
            while (set.contains(currentChar)) {
                // a 指针开始移动，把左边的字符从记事本里删掉
                set.remove(s.charAt(a));
                // a 向右挪，直到把那个重复的字符“挤”出去
                a++;
            }
            
            // 现在窗口里肯定没有 currentChar 了，把它加进去
            set.add(currentChar);
            
            // 更新最大长度：窗口大小就是 b - a + 1
            maxLength = Math.max(maxLength, b - a + 1);
            
            // b 继续前进
            b++;
        }
        
        return maxLength;
    }
}

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        int maxLength = 0;
        // Key: 字符, Value: 字符最后一次出现的下标
        Map<Character, Integer> map = new HashMap<>();

        // a 是左指针，b 是右指针
        for (int a = 0, b = 0; b < n; b++) {
            char currentChar = s.charAt(b);

            // 如果发现重复字符
            if (map.containsKey(currentChar)) {
                /* * 关键点：a 直接跳到重复字符上次出现位置的下一个。
                 * 为什么用 Math.max？
                 * 因为 map 里的记录可能在当前窗口 a 的左边（即没被 remove 掉的僵尸记录），
                 * 我们绝对不能让 a 往回跳！
                 */
                a = Math.max(a, map.get(currentChar) + 1);
            }

            // 更新或记录当前字符的最新的位置
            map.put(currentChar, b);
            
            // 计算长度并更新最大值
            maxLength = Math.max(maxLength, b - a + 1);
        }
        return maxLength;
    }
}

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        int sLen = s.length(), pLen = p.length();
        if (sLen < pLen) return result;

        // 1. 记录目标字符串 p 的字符频率
        int[] pCount = new int[26];
        int[] sCount = new int[26];
        for (int i = 0; i < pLen; i++) {
            pCount[p.charAt(i) - 'a']++;
        }

        // 2. 双指针移动
        int left = 0;
        for (int right = 0; right < sLen; right++) {
            // 将右边界字符加入当前窗口频率
            sCount[s.charAt(right) - 'a']++;

            // 3. 当窗口长度大于 pLen 时，左边界右移，并从频率中减去
            if (right - left + 1 > pLen) {
                sCount[s.charAt(left) - 'a']--;
                left++;
            }

            // 4. 检查两个频率数组是否完全相同
            // 因为窗口长度固定为 pLen，只要频率一致，就一定是异位词
            if (Arrays.equals(sCount, pCount)) {
                result.add(left);
            }
        }
        return result;
    }
}

import java.util.*;

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        int sLen = s.length(), pLen = p.length();
        if (sLen < pLen) return result;

        // count 数组记录 s 窗口与 p 之间字符频次的“差值”
        // count[i] > 0 表示 s 窗口里比 p 多
        // count[i] < 0 表示 s 窗口里比 p 少（即还欠 p 多少个）
        int[] count = new int[26];
        for (int i = 0; i < pLen; i++) {
            count[p.charAt(i) - 'a']--; // 初始化：p 中的字符都算作“欠下的”
            count[s.charAt(i) - 'a']++; // 初始化：把 s 开头的窗口填入
        }

        // 统计初始状态下，有多少个字母的频次是不匹配的
        int differ = 0;
        for (int c : count) {
            if (c != 0) differ++;
        }

        // 检查第一个窗口是否匹配
        if (differ == 0) result.add(0);

        // 滑动窗口开始
        for (int i = 0; i < sLen - pLen; i++) {
            // 1. 窗口左边界移除 s[i]
            int leftChar = s.charAt(i) - 'a';
            if (count[leftChar] == 1) { // 原本多一个，现在减去变平衡了
                differ--;
            } else if (count[leftChar] == 0) { // 原本平衡，现在减去变不平衡了
                differ++;
            }
            count[leftChar]--;

            // 2. 窗口右边界加入 s[i + pLen]
            int rightChar = s.charAt(i + pLen) - 'a';
            if (count[rightChar] == -1) { // 原本缺一个，现在补上变平衡了
                differ--;
            } else if (count[rightChar] == 0) { // 原本平衡，现在加入变不平衡了
                differ++;
            }
            count[rightChar]++;

            // 3. 如果差异值为 0，说明找到了一个异位词
            if (differ == 0) {
                result.add(i + 1);
            }
        }

        return result;
    }
}

输入：nums = [1,1,1], k = 2
输出：2

输入：nums = [1,2,3], k = 3
输出：2

class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0;
        int sum = 0;
        int a = 0; // 左指针

        // b 为右指针，不断扩大窗口
        for (int b = 0; b < nums.length; b++) {
            sum += nums[b]; // 扩大窗口，累加和

            // 当窗口内和大于 k 时，尝试缩减窗口（左指针右移）
            while (sum > k && a < b) {
                sum -= nums[a];
                a++;
            }

            // 检查当前窗口和是否满足条件
            if (sum == k) {
                count++;
            }
        }

        return count;
    }
}

class Solution {
    public int subarraySum(int[] nums, int k) {
        // Key: 前缀和, Value: 该前缀和出现的次数
        Map<Integer, Integer> map = new HashMap<>();
        
        // 【关键点】初始化：前缀和为 0 出现了一次。
        // 这一步是为了处理那些“从数组起始位置开始”就满足条件的子数组
        // 比如 nums=[3], k=3。当前 pre=3, target=0。如果 map 里没记 0，就会漏掉。
        map.put(0, 1);
        
        int count = 0;
        int preSum = 0;
        
        for (int num : nums) {
            preSum += num; // 1. 计算当前位置的前缀和
            
            // 2. 核心公式：寻找是否存在历史前缀和 = preSum - k
            if (map.containsKey(preSum - k)) {
                count += map.get(preSum - k);
            }
            
            // 3. 将当前的前缀和记录到 map 中，或者更新出现次数
            map.put(preSum, map.getOrDefault(preSum, 0) + 1);
        }
        
        return count;
    }
}