GO实现无重复字符的最长字串（map+滑动窗口）

秒速五厘米 2022-12-24 15:53 135阅读 0赞

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。  
此题来源于：力扣  
首先，此题归根到底，是查找字符串的重复值。如果重复，返回不重复字符串的最大长度  
我们可以进行双指针进行遍历字符串，并且将遍历到的字符进行记录。进行查重。

func lengthOfLongestSubstring(s string) int {
        
    	if len(s) ==0 {
        //判断字符串的长度，如果为空，则返回0
    		return 0
    	}
        if len(s) == 1{
        //字符串的长度为1，则也不会重复，直接返回
            return 1
        }
    	des := make(map[byte]int)//声明map，并且将遍历到的字符作为索引，值为int型变量，将遍历的字符在map中进行+1操作
    	max := 0//记录最大长度
    	i, j := 0, 1//双指针，前指针指向首元素，后指针指向第二元素
    	flage := 0//设置标记
    	des[s[i]]++//首先先将第一个字符所对应到的字符在map上进行+1
    	for j < len(s) && i < len(s) {
        //for循环，在两指针都小于数组长度的情况下
    		if flage == 0 {
        //判断flage是否为0，如果为0，进行后指针+1操作
    			des[s[j]]++
    		}
    		if des[s[j]] > 1 {
        
    		//判断后指针指向的元素是否大于一，如果大于一，则证明出现过大于一次，
    		//则进行前指针移动。但是注意，如果此时前指针向后移动，后指针不移动，
    		//则在进行下一个循环时，还会进行后指针+1操作，所以，此时需要flage=1，在下次循环时，不会进行后指针所对应的值+1操作
    			if j-i > max {
        
    				max = j - i//判断，如果此序列的长度大于之前的max长度，则将更改max操作
    			}
    			des[s[i]]--//因为前指针即将向后移动，前指针移动之后，意味着前指针指向的字符没有出现，则需要前指针指向的字符所对应的map进行 -1操作
    			i++//前指针向后移
    			flage = 1//设置标记为1，如果不设置，则下次循环，后指针不动，还会进行+1操作。导致一个字符，被记录多次
    		} else {
        
    			j++//如果后指针指向的字符与到前指针的字符都不相同，则后指针进行+1操作
    			if j == len(s) {
        //判断，如果后指针已经到最后一位，则判断，后指针与前指针索引差，如果大于max返回j-i，如果不大于max，返回max
    				if j-i>max{
        
                        return j-i
                    }else{
        
                        return max
                    }
    			}
    			flage = 0//由于后指针移动，所以flage被标记为0，到下次循环时，应该j指针被+1。
    		}
    	}
    	return max//返回max
    }

进行滑动窗口解题所用时间和消耗的内存  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1hpYW5nX2xoaA_size_16_color_FFFFFF_t_70]

此题总的来说，可以滑动窗口，再加map查重，结合进行。  
也可以进行暴力进行解题，但是相对于速度，慢很多  
暴力解题法：  
暴力解法，不进行过多解释，双层for循环。再加一个判断字符是否之前出现过。

func lengthOfLongestSubstring(s string) int {
        
    	max := 0
    	length := len(s)
    	similar := make([]string, 0)
    	for i := 0; i < length; i++ {
        
    		similar = similar[0:0]
    		similar = append(similar, string(s[i]))
    		for k := i + 1; k < length; k++ {
        
    			if Is_in(similar, string(s[k])) {
        
    				break
    			} else {
        
    				similar = append(similar, string(s[k]))
    			}
    		}
    		if max < len(similar) {
        
    			max = len(similar)
    		}
    	}
    	return max
    }
    func Is_in(con []string, dis string) bool {
        
    	length := len(con)
    	if length == 0 {
        
    		return false
    	}
    	for i := 0; i < length; i++ {
        
    		if dis == string(con[i]) {
        
    			return true
    		}
    	}
    	return false
    }

进行暴力算法所需要的时间和占用内存大小  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1hpYW5nX2xoaA_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1hpYW5nX2xoaA_size_16_color_FFFFFF_t_70]: /images/20221120/a28121b766734a90b326dd6fde1f0334.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1hpYW5nX2xoaA_size_16_color_FFFFFF_t_70 1]: /images/20221120/d8022207e6694c19bea92a233ab6c358.png