【LeetCode】3.无重复字符的最长子串（滑动窗口）

简书内代码已上传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