查找最长无重复字符串子串编程问题

柔情只为你懂 2022-01-30 07:59 191阅读 0赞

给定一个字符串  “abccabd”，查找出没有重复字符的字符串子串的最大长度。

主要应用了滑窗移动的思想，需要提前创建一个Hashset 集合来存储字符串。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5NjYwOTU3_size_16_color_FFFFFF_t_70][]

定义一个区间\[i，j\]，i和j的初始值都为0，开始每次j向右移动一格，判断此时的字符是否在前面创建的Hashset中存在，如果不存在则将这个字符加入创建好的Hashset中，同时记录此时的长度，与上一个记录的长度比较取最大值。

当j向右移动一格找到的字符存在已有的集合中时，将逐渐移除这个集合中的前面的字符，直到移除了此时标记了的字符。

具体代码如下

public class lengthOfLongestSubstring {
    
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		String str ="aaabcbxfsasd";
    		System.out.println(lengthOfLongestSubstring(str));
    	}
    
    	private static int lengthOfLongestSubstring(String str) {
    		// TODO Auto-generated method stub
    		int len=0;
    		int strlength = str.length();
    		int i=0;
    		int j=0;
    		HashSet<Character> hs = new HashSet<Character>();
    		while(i<strlength&&j<strlength) {
    			if(!hs.contains(str.charAt(j))) {
    				hs.add(str.charAt(j++));
    				len =Math.max(len, j-i);
    			}else {
    				hs.remove(str.charAt(i++));
    			}
    		}
    		return len;
    	}
    	
    }

更新使用map来存储数值，以达到简化代码的作用

class Solution {
        public int lengthOfLongestSubstring(String s) {
            int n = s.length(), ans = 0;
            Map<Character, Integer> map = new HashMap<>();
            for (int end = 0, start = 0; end < n; end++) {
                char alpha = s.charAt(end);
                if (map.containsKey(alpha)) {
                    start = Math.max(map.get(alpha), start);
                }
                ans = Math.max(ans, end - start + 1);
                map.put(alpha, end + 1);
            }
            return ans;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5NjYwOTU3_size_16_color_FFFFFF_t_70]: /images/20220130/03e5c913ffff48e6a85916831fc71dc1.png