leetcode-无重复字符的最长子串

无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。

示例 1:

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

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

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

提示：

0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成

def lengthOfLongestSubstring(self, s: str) -> int:
    # 写一个滑动窗口
    # 开始的时候左面指针是0
    # 每次移动右面元素，判断窗口内元素是否合法，如果不合法就移动左指针直到合法
    # 如何判断窗口内元素是否合法？使用字典或者set
    left = 0
    max_size = 0
    char_set = set()
    for right in range(len(s)):
        if s[right] in char_set:
            while s[right] in char_set:
                char_set.remove(s[left])
                left += 1
        
        char_set.add(s[right])
        max_size = max(max_size, len(char_set))

    return max_size

核心问题：

如何快速判断窗口内有没有重复？用 HashSet / hashmap 记录窗口内容

Step 1：右指针扩张 不断加入新字符。
Step 2：如果重复 左指针一直移动直到合法
Step 3：更新最大长度

核心思想就是：先扩张，再修复
对于固定窗口就简单了，就是right++ → left++

长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果> 不存在符合条件的子数组，返回 0 。

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：

输入：target = 4, nums = [1,4,4]
输出：1
示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

提示：

1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 104

暴力解法 o(n2)

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        for i in range(1, len(nums)+1):
            left, right = 0, i
            while right <= len(nums):
                if sum(nums[left:right]) >= target:
                    return i
                left+=1
                right+=1
        return 0

利用双指针解法：

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        left = 0
        min_len = float("inf")
        window_sum = 0
        # right 扩张 → 找到合法窗口
        for right in range(len(nums)):
            window_sum += nums[right]
            # left 收缩 → 找到更优解
            while window_sum >= target:
                min_len = min(min_len, right - left + 1)
                window_sum -= nums[left]
                left += 1
        return 0 if min_len == float("inf") else min_len

滑动窗口依赖于窗口扩大和缩小时，状态具有单调性。
当数组全部是正数时，窗口扩大 sum 一定增加，窗口缩小 sum 一定减少，因此可以安全移动指针。
如果存在负数，这种单调性被破坏，滑动窗口就不再适用。