首页 > 其他 > 详细

Longest Substring Without Repeating Characters,求没有重复字符的最长字串

时间:2016-08-21 19:46:14      阅读:169      评论:0      收藏:0      [点我收藏+]

问题描述:

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.

算法分析:使用滑动窗口,设置两个指针,遍历字符串。

public class LongestSubstringWithoutRepeatingCharacters {
	public int lengthOfLongestSubstring(String s)
	{
		int n = s.length();
		Set<Character> set = new HashSet<>();
		int ans = 0, i = 0, j = 0;//窗口左右指针
		while(i < n && j < n)
		{
			if(!set.contains(s.charAt(j)))
			{
				set.add(s.charAt(j++));
				ans = Math.max(ans, j - i);
			}
			else//如果有重复元素,则窗口左指针向右移动,直到移动到重复元素的下一位
			{
				set.remove(s.charAt(i++));
			}
		}
		return ans;
	}
}

  

Longest Substring Without Repeating Characters,求没有重复字符的最长字串

原文:http://www.cnblogs.com/masterlibin/p/5793217.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!