窗口简书内代码已上传GitHub:点击我 去GitHub查看代码
点击 这里跳转到LeetCode官网查看题目
点击 这里跳转到LeetCode中国官网查看题目
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
思路:
- 滑动窗口算法在我看来就是一个特殊的双指针解法
先来回顾一下经典的双指针解法:有序序列的两数和问题,我们可以令初始的左右指针分别在序列两端,如果和大于所求值,右指针左移。如果和小于所求值,左值针右移:
//伪码
while(){
if(sum > need)
r--;
else
l++;
}
-
而这一题,我们需要找到的是一段范围,我们可以形象的理解为一个窗口。而同样的利用双指针,我们初始时左右指针都在左端,如果窗口内没有重复元素,右指针向右移动。如果移动后有重复元素了,左值针右移,直到窗口内没有重复元素。
-
左值针右移 十分关键,如果是暴力法,那对于字符串中每一个元素,我们都要对它进行再一次的向后遍历,时间复杂度是非线性的。首先扩大窗口,在确保窗口内没有重复元素的时候,这就是这段窗口内最大的无重复区域,所以窗口内已经无需再次搜索,这也是滑动窗口的精髓。所以上一点写道,可以左值针右移,直到窗口内没有重复元素。
大家有没有觉得双指针问题其实都差不多,重点就是指针移动的条件,弄清楚后,题目也就解决了。
Accept by C:
#define max(x, y)(x > y ? x : y)
// 滑动窗口算法
int lengthOfLongestSubstring(char * s){
// 定义左右指针
int l, r;
l = 0; r = -1;
//cnt存储出现次数
int cnt[256] = {0};
//获取长度
int len = strlen(s);
int maxsize = 0;
while(l < len){
// 边界限定以及右指针移动条件
if( (r + 1 < len) && (cnt[s[r + 1]] == 0) )
++cnt[s[++r]];
else
//左值针移动条件刚好与右指针互斥,即有重复元素移动左值针
--cnt[s[l++]];
maxsize = max(maxsize, r - l + 1);
}
return maxsize;
}
每天进步一点,加油!
End
END
网友评论