10.《滑动窗口篇》---②长度最小的子数组（中等）

有了上一篇的基础。这道题我们就可以轻易分析可以使用滑动窗口来解决了

方法一：滑动窗口

这里注意 ret 在while循环外部更新

在 while 外部更新 ret，确保窗口在满足条件后再计算长度，避免错误计入正在调整中的窗口长度。

class Solution {
    public int lengthOfLongestSubstring(String s0) {
        int[] hash = new int[128]; //数组模拟哈希表
        int n = s0.length();
        char[] s = s0.toCharArray();
        int ret = 0;

        for(int left = 0,right = 0; right < n; right++){
            hash[s[right]]++; //进入窗口
            while(hash[s[right]] > 1){
                hash[s[left++]]--;
            }
            ret = Math.max(ret,right-left+1);
        }
        return ret;
    }
}

复杂度分析

时间复杂度：O（n），

空间复杂度：

• 常见分析: 空间复杂度为 O(1)，因为哈希表是固定大小，额外空间使用与输入大小无关。
• 严格分析: 如果字符数组 chars 被视为额外空间，则空间复杂度为 O(n)

原文地址：https://blog.csdn.net/m0_73456341/article/details/143877811

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！