面试经典 150 题 |
您所在的位置：网站首页 › 滑动窗口计算题 › 面试经典 150 题 |
面试经典 150 题
|
面试经典150题链接
面试经典 150 题 - 学习计划 - 力扣（LeetCode）全球极客挚爱的技术成长平台 
209 . 长度最小的子数组
思路 :
滑动窗口的思想，取i=j=0,向后遍历j,记录前缀和[l,r]为s,如果s>=target,那么左端点向右移动，直到s int: n = len(nums) ans = n+1 l=0 s=0 for r,x in enumerate(nums): s+=x while s>=target: ans = min(ans,r-l+1) s-=nums[l] l+=1 return ans if ans = target){ ans = min(ans , r - l + 1) ; sum -= nums[l++]; } r++ ; } return ans == INT_MAX ? 0 : ans ; } }; 3 . 无重复字符的最长子串 思路 : 假设在一个无重复元素的字符串后面加上一个字符，如果出现重复元素，那么一定重复的是新加上的那个字符，那么设置一个hash表来统计次数，然后反复将窗口最前面的元素移出窗口，直到将前面与新加元素相同的元素移出时停止；然后循环更新答案即可； lc题解地址 :力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 代码 ： Python class Solution: def lengthOfLongestSubstring(self, s: str) -> int: l = 0 cnt = Counter() ans = 0 for r , c in enumerate(s): cnt[c]+=1 while cnt[c]>=2: cnt[s[l]]-=1 l+=1 ans = max(ans,r-l+1) return ans C++ class Solution { public: int lengthOfLongestSubstring(string s) { unordered_map hash; int ans=0; int n = s.size(); int l=0; for(int r=0;r 1) --hash[s[l++]]; ans = max(ans,r-l+1); } return ans; } }; java class Solution { public int lengthOfLongestSubstring(String s) { int ans = 0 ; char[] st = s.toCharArray(); boolean[] has = new boolean[128] ; int n = s.length(); int i = 0 ; for(int j=0;j c1[j]c2[j]>c1[j] 的检查，直到窗口不能再收缩 若不满足：说明当前窗口没有任何一个后缀字符串能够实现对 t 的覆盖，我们并不能对窗口实现收缩 每次对窗口移动完成后，我们检查当前 tot 是否为 000（对字符串 t 的覆盖是否完成），若为 000 则尝试用当前窗口对应的字符串 s[j...i]s[j...i]s[j...i] 更新 ans。 class Solution { public: int get(char x) { return x >= 'A' && x i-j+1)) ans = s.substr(j,i-j+1); } return ans ; } }; 相似题目 :力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 |
【本文地址】
今日新闻 |
推荐新闻 |