Leetcode平台上的LongestSubstringWithoutRepeatingCharacters用Java贪心算法实现

该题目就是求最长的无重复字符的子串。

一开始简单粗暴的用两层循环实现了，结果可想而知，超时。。。

谢谢度娘，谢谢各位大牛前辈，用贪心算法，一层循环实现，效率不错,O(n)

last数组简直神一般存在，完美解决我两层循环的问题！！

贪心算法不是万能的，有些情况就不使用，比如局部最优解，最后可能并非全局最优解。

本题目中，最长无重复子串肯定包含在两个重复字符之间，用len保存当前最长的子串。如果某两个重复字符之间的子串长于len,则给len赋值这个新的长度。

源代码如下：


public class Solution {
    //测试用例的字符从空格到大写字母Z，所以128足够了
    static int[] last = new int[128];
    public static int lengthOfLongestSubstring(String s){
        int start = 0;
        int len = 0;
        char[] w = new char[s.length()];
        w = s.toCharArray();
        for(int i = 0; i < 128; i++)
            last[i] = -1;//last数组用于保存新出现的字符的下标，一开始全部初始化为-1
        for(int i = 0; i < s.length(); ++ i){
            if(last[w[i]-' '] >= start){ //当前这个字符出现过
                if(i-start > len)
                    len = i-start;
                start = last[w[i]-' '] + 1; //从这个字符首次出现的位置+1，重新扫描，相当于把前面抛开前面的字符串不谈
            }
                last[w[i]-' '] = i;//更新当前字符的下标
        }
        if(len > s.length() - start)//针对没有重复字符的字符串
            return len;
        else
            return s.length() - start;
    }
   
    public static void main(String args[]){
        String s ="wlrbbmqbhcdarzowkkyhiddqscdxrjmowfrxsjybldbefsarcbynecdyggxxpklorellnmpapqfwkhopkmco";
        int l = lengthOfLongestSubstring(s);
        System.out.println(l);
    }   
}