欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode_3 “无重复字符的最长字串”

程序员文章站 2022-04-04 09:59:25
...

题目描述
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。

示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。

解题思路
拿到这道题的第一想法就是暴力解法,枚举所有可能的子串情况,在其中找到最长的子串。我是结合HashMap来实现的,具体的思路就是:设置双重循环,外层以每一个字符为起点进行最长子串的寻找,内层遍历该起点之后的字符,若与之前没有重复的字符,则将该字符添加到HashMap中,最长子串的长度+1,若与之前有重复的字符,则清空HashMap,跳出内层循环,以下一个字符为起点进行寻找。代码如下所示:

public int lengthOfLongestSubstring(String s) {
		int length = 0;
		Map<String,Boolean> map = new HashMap<String,Boolean>();
		for(int i=0; i<s.length(); i++) {
			int tmp = 0;
			for(int j=i; j<s.length(); j++) {
				String str = s.substring(j,j+1);
				if(map.get(str) == null) {	// 哈希表中不存在该字符
					map.put(str, true);	
					tmp ++;
					if(tmp > length) {
						length = tmp;
					}
				} else {	// 存在重复字符
					map.clear();
					break;
				}
			}
		}
		return length;
    }

提交之后,代码通过了。但是效率并不高,进一步学习之后发现了更好更高效的方法:滑动窗口。由于小编也是第一次听说这个概念,进行初步的学习之后也算是有了一些了解。它是数组和字符串问题中常用的抽象概念,其本质就是在使用两个指针ij卡在窗口的两边,然后使窗口沿着某一方向滑动,比如我们将窗口[i,j)向右滑动一个单位,窗口就变为[i+1,j+1)。结合我们这道题目来说,定义窗口[i,j)(最初i=j),然后不断滑动j寻找最长子串,如果遇到有重复的字符,就滑动i,确保窗口内永远是没有重复字符的。如下如所示:
LeetCode_3 “无重复字符的最长字串”
代码如下:

public int method_3(String s) {
		int n = s.length(), ans = 0;
		Map<Character,Integer> map = new HashMap<>();
		for(int j=0, i=0; j<n; j++) {
			if(map.containsKey(s.charAt(j))){
				i = Math.max(map.get(s.charAt(j)), i);
			}
			ans = Math.max(ans, j-i+1);
			map.put(s.charAt(j), j+1);
		}
		return ans;
	}
相关标签: Java 算法