无重复字符的最长子串

无重复字符的最长子串(哈希leetcode3)--------------c++/java实现 题目表述

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

样例

输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

条件

0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成

思路

使用c++stl中的unordered_set 哈希表 使得查找字符大概在O(1)时间复杂度内解决，从左往右让字符加入该哈希表中，查出重复则从左往右推出哈希并且删除不可组成无重复字符串的相关字符。

java则使用hashset，原理同c++中的unorder_set

注意点

注意判断条件和跳出条件。

ac代码 c++：

#include 
#include
#include
using namespace std;
class Solution
{
public:
    int lengthOfLongestSubstring(string s)
    {
        unordered_set<char> original;
        int slongth=s.size();
        int max=0,begin=0,sum=0;
        for(int i=0; i<slongth; i++)
        {
            if(original.count(s[i]))
               {
                   while(s[begin]!=s[i])
                {
                    original.erase(s[begin]);
                        begin++;
            }
            begin++;
               }
                  else
                original.insert(s[i]);
                if(original.size()>max)
                max=original.size();
        }
        return max;
        }
};
int main(int argc, char** argv)
{
    Solution s=Solution();
    cout<<s.lengthOfLongestSubstring("aabaab!bb");
}

java：

class Solution {
    public int lengthOfLongestSubstring(String s) {
		    HashSet<Character> a = new HashSet<Character>();
		    int size=s.length();
		    int begin=0,max=0;
		    for(int i=0;i<size;i++) {
		    	if(a.contains(s.charAt(i))) {
		    		while(s.charAt(begin)!=s.charAt(i)) {
		    			a.remove(s.charAt(begin));
		    			begin++;
		    		}
		    		begin++;
		    	}
		    	else 
		    		a.add(s.charAt(i));
                    if(a.size()>max)
		    		max=a.size();
		    }
                return max;
	    }
}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/squares-of-a-sorted-array
著作权归领扣网络所有。

商业转载请联系官方授权，非商业转载请注明出处。