209. 长度最小的子数组 - 力扣（LeetCode） (opens new window)

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0;
        int sum = 0;
        int minLen = Integer.MAX_VALUE;
        for (int right = 0; right < nums.length; right++) {
            // 扩展窗口
            sum += nums[right];
             // 满足条件时收缩窗口
            while (sum >= target) {
                minLen = Math.min(minLen, right - left + 1);
                // 左指针右移，缩小窗口
                sum -= nums[left++];
            }
        }
        return minLen == Integer.MAX_VALUE ? 0 : minLen;
    }
}

前缀和+二分查找

// todo
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int[] prefixSum = new int[n + 1];
        int minLen = Integer.MAX_VALUE;
        // 前缀和数组下标从1开始，prefixSum[i] 表示 nums[0] 到 nums[i-1] 的和
        for (int i = 1; i <= n; i++) {
            prefixSum[i] = prefixSum[i - 1] + nums[i - 1];
        }
        // 二分查找目标：prefixSum[j] - prefixSum[i] >= target 的最小 j
        for (int i = 0; i < n; i++) {
            int left = i, right = n;
            while (left < right) {
                int mid = left + (right - left) / 2;
                // 若子数组和小于目标值，说明当前区间 [i, mid] 的和不足，需​​扩大右边界​​以包含更多元素（即 left = mid + 1）
                // 若子数组和达到或超过目标值，说明当前区间可能满足条件，需​​缩小右边界​​以尝试找到更短的子数组（即 right = mid）
                if (prefixSum[mid + 1] - prefixSum[i] < target) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            if (right != n) {
                minLen = Math.min(minLen, left - i + 1);
            }
        }
        return minLen == Integer.MAX_VALUE ? 0 : minLen;
    }
}

3. 无重复字符的最长子串 - 力扣（LeetCode） (opens new window)

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> window = new HashMap<>();
        int left = 0, right = 0;
        int res = 0;
        while (right < s.length()) {
            char c = s.charAt(right);
            right++;
            // 进行窗口内数据的一系列更新
            window.put(c, window.getOrDefault(c,0) + 1);
            // 判断左侧窗口是否要收缩
            while (window.get(c) > 1) {
                char d = s.charAt(left);
                left++;
                // 进行窗口内数据的一系列更新
                window.put(d, window.getOrDefault(d,0) - 1);
            }
            // 在这里更新答案
            res = Math.max(res, right -left);
        }
        return res;
    }
}

**拼多多：**最多允许一对相邻重复字符的最长子串问题

public class Solution {
    public int longestSubstring(String s) {
        if (s == null || s.length() == 0) return 0;
        int left = 0, maxLen = 1, repeatCount = 0;
        
        for (int right = 1; right < s.length(); right++) {
            // 检查当前字符与前一个是否重复
            if (s.charAt(right) == s.charAt(right - 1)) {
                repeatCount++;
            }
            
            // 若相邻重复次数超过1，移动左指针直到合法
            while (repeatCount > 1) {
                if (s.charAt(left) == s.charAt(left + 1)) {
                    repeatCount--;
                }
                left++;
            }
            
            // 更新最大长度
            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }
}