java 最长不重复子串,最长无重复字符子串

谁借莪１个温暖的怀抱￠ 2022-12-24 15:59 203阅读 0赞

正文在下面，先打个广告：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZneWlidXBp_size_16_color_FFFFFF_t_70]  
问题描述：  
输入：abdca 返回：abdc

方法一：使用双指针（滑动窗口）来实现。该方法需要配合map保存已经出现过的字符。

public static int maxLength(String nums, int begin, int end, int maxStr){ 
            if (null == nums || nums.length() == 0) return 0;
            if (end>=nums.length()) return maxStr;
            Map<Character, Integer> map = new HashMap<>();
            for (int i = begin; i <= nums.length()-1 ; i++) { 
                if (null == map.get(nums.charAt(i))) { 
                    map.put(nums.charAt(i), i);
                    if(map.size() > maxStr){ 
                        maxStr = map.size();
                    }
                } else { 
                    begin = map.get(nums.charAt(i)) + 1;
                    break;
                }
            }
            return maxLength(nums, begin, end+1, maxStr);
        }
    public static void main(String[] args) { 
            System.out.println(maxLength("arabcacfr",0,1,1));
            System.out.println(maxLength("aababcbcd",0,1,1));
            System.out.println(maxLength("ccccc",0,1,1));
            System.out.println(maxLength("",0,1,1));
            System.out.println(maxLength("c",0,1,1));
            System.out.println(maxLength("ac",0,1,1));
            System.out.println(maxLength(null,0,1,1));
    }

测试结果：

4
    3
    1
    0
    1
    2
    0

方法二：使用动态规划，记录当前字符之前的最长非重复子字符串长度f(i-1)，其中i为当前字符的位置。每次遍历当前字符时，分两种情况：

1）若当前字符第一次出现，则最长非重复子字符串长度f(i) = f(i-1)+1。  
2）若当前字符不是第一次出现，则首先计算当前字符与它上次出现位置之间的距离d。若d大于f(i-1)，即说明前一个非重复子字符串中没有包含当前字符，则可以添加当前字符到前一个非重复子字符串中，所以，f(i) = f(i-1)+1。若d小于或等于f(i-1)，即说明前一个非重复子字符串中已经包含当前字符，则不可以添加当前字符，所以，f(i) = d。

**关键点：** 动态规划，两个重复字符的距离

public static int maxLength(String str) { 
            if(str==null || str.equals(""))
                return 0;
    
            int maxLength=0;
            int curLength=0;
            int[] position = new int[26];
            for(int i=0;i<position.length;i++) { 
                position[i]=-1; //初始化为-1，负数表示没出现过
            }
    
            for(int i=0;i<str.length();i++) { 
                int prevIndex = position[str.charAt(i)-'a'];
                int distance=i-prevIndex;
    
                //如果当前字符没有出现过，或者出现后的d大于当前最长字串长度
                if(prevIndex<0 || distance>curLength)
                    curLength++;
                else {  //如果d<=当前最长字串长度，说明两个相同字符在最长字串中
                    if(curLength > maxLength)
                        maxLength = curLength;
    
                    curLength = distance;
                }
                position[str.charAt(i)-'a'] = i; //更新当前字符出现的位置
            }
    
            if(curLength>maxLength)
                maxLength=curLength;
    
            return maxLength;
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZneWlidXBp_size_16_color_FFFFFF_t_70]: /images/20221120/0e5c9b1541ea472ca691b035f88e79b5.png