LeetCode 3 Longest Substring Without Repeating Characters

1年前 (2017-05-12) wang LeetCode 0评论 已收录 219℃ 浏览数:81

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

这个题目是我一看到就比较有思路的,用一个HashMap来存每个字符,存的时候判断当前的HashMap中是否含有这个字符,如果存在的话,我第一次只是删除前一个字符,然后慢慢觉得不对。于是我改为如果有的话就清空HashMap,然后再次存值。 但是有一个问题 dvdf 像这种出现了d重复,并不是d前面的字符都不要,而是从上一个d的下一个字符开始重新计数。

于是写出的代码如下。


public class Solution {
    public int lengthOfLongestSubstring(String s) {
      HashMap<Character, Integer> map = new HashMap<Character, Integer>();
		int len = s.length();
		int i = 0, j = 0, max = 0;
		while (i < len) {
			if (map.containsKey(s.charAt(i))) {
				j = Math.max(j, map.get(s.charAt(i)));
			}
			
			map.put(s.charAt(i), i);
			max = Math.max(max, i - j);
			i++;

		}

		return max;
    }
}

思路就是遍历添加每个字符,遇到重复的字符,取它在map中所在的位置存到j中,最后判断i-j的最大值,我感觉是没有什么问题的,但是提交wa,发现是单个字符出现了问题。因为数组下表是0,于是修改后如下。


public class Solution {
    public int lengthOfLongestSubstring(String s) {
      HashMap<Character, Integer> map = new HashMap<Character, Integer>();
		int len = s.length();
		int i = 0, j = 0, max = 0;
		while (i < len) {
			if (map.containsKey(s.charAt(i))) {
				j = Math.max(j, map.get(s.charAt(i)) + 1);
			}
			
			map.put(s.charAt(i), i);
			max = Math.max(max, i - j +1);
			i++;

		}

		return max;
    }
}

取出j的值的时候加了1,i-j的时候也加了1,这样就解决了单个字符的问题,提交后ac。

然后查看实例代码,发现有人用HashSet来判断,这样的话。思路是,int j用来删除字符,首先遍历字符串,不重复的字符加入HashSet,然后如果遇到重复的则从j++开始删除,一直删除到没有重复字符,然后添加该字符,判断Hashset的长度,取最大的大小。开始没有明白是如何进行删除的,进行思考后。假设是这个字符串 dvdf 。先存d,然后v,然后发现d重复,就会从j++开始删除,第一个就删除掉第一个d,然后就HashSet里就没有d字符了,然后再添加,最后HashSet中就存了vdf。跟用HashMap的思路是差不多的。Map是取出开始计数的值,Set是删除重复的值。

public class Solution {
    public int lengthOfLongestSubstring(String s) {
       HashSet<Character&gt; set = new HashSet&lt;Character&gt;();
		int len = s.length();
		int i = 0, j = 0, max = 0;
		while (i &amp;amp;lt; len) {
			if (set.contains(s.charAt(i))) {
				set.remove(s.charAt(j++));
			} else {
				set.add(s.charAt(i++));
				max = Math.max(max, set.size());
			}
		}

		return max;
    }
}
博主

Just do it. Now or never.

相关推荐

嗨、骚年、快来消灭0回复。