笔试面试题目：滑动窗口(一)

算法：

这是滑动窗口的经典题目，通过题目我们可以将题目拆解成两步：

一、如何进行窗口的滑动。

这里我们可以采用双指针的方法，left不变的时候， 找到不重复的元素的右指针位置，那么窗口大小为right-left+1。

二、如何进行重复元素的判断。

我们采用hash的方式， 也就是golang中的map。 1.在移动left的时候，我们从map中移除没有移动之前的元素，也就是left-1那个位置的元素。 2.在移动right的时候，只要right对应的元素在map不存在，那么就存到map里面，并且后移right; 否则跳出循环，这里的right也就是本次窗口的最右侧位置。

题目： https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

leetcode的官方题目分析：

代码实现：

func lengthOfLongestSubstring(s string) int {    // map用来判断是不是有重复的元素 m := map[byte]int{} num := len(s)    // 右指针=-1表示什么都没操作，窗口大小一定>0，所以这里初始化为0 right,result := -1,0 for left :=0;left<num;left++ { if left != 0 {        // 左指针向右移动一格，移除前面的那一个元素，例如：left =1之后，移除left=0的元素 delete(m,s[left-1]) }        // 每一次操作，右指针从[left,right]都是不重复的元素了，所以从right=1开始 for right+1<num&&m[s[right+1]]==0{ right++ m[s[right]]++ } result = max(result,right-left+1) } return result } func max(num1, num2 int) int { if num1>num2 { return num1 } return num2 }

执行结果：

备注：这里双指针的解决并不是滑动窗口的最优解法，不过确实最常用的解法，也比较容易想到，这也是笔者整理这一思路的主要原因。