題目： Longest Substring Without Repeating Characters

原題描述:
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.

題目提煉

計算給定字符串的不含有重復(fù)元素的字串的最大長度励稳。

分析

首先這應(yīng)該是一道與串相關(guān)的算法題佃乘，這里只要求返回最大長度驹尼，那么肯定會有一個變量tmp記錄每一次更新后趣避，當前滿足條件的字串的長度扶欣。還有一個變量result用來記錄當前滿足條件的字串的最大長度，每次操作后料祠，都需要比較tmp與result的大小進而更新result骆捧。還需要一個集合來對已經(jīng)讀取的字符進行緩存，這里有一個值得注意的地方：當發(fā)現(xiàn)緩存的字符集包含了當前讀取的字符時髓绽，可以將字符集中第一個字符到重復(fù)字符的部分截取敛苇，再將當前字符加入字符集中顺呕。出于這一特性，可以使用list作為緩存字符集的容器株茶，這里在代碼是線上有一個優(yōu)化来涨，就是將當前讀取的字符是否與已讀字符重復(fù)作為result更新的條件，然后在循環(huán)結(jié)束后再比較一次启盛，防止循環(huán)中一次更新都沒有做的情況蹦掐。這樣不用每次循環(huán)都去比較result和tmp的大小。

代碼如下：

public int lengthOfLongestSubstring(String s) {
        int tmp=0;
        int result=0;
        int begin=0;
        Character a=null;
        List<Character> list=new ArrayList<>();
        //Set<Character> set=new HashSet();
        for ( int i=0;i<s.length();i++){
            a=new Character(s.charAt(i));
            if(!list.contains(a)){
                tmp++;
                list.add(a);
            } else {
                if(tmp>result)
                    result=tmp;
                int j=list.indexOf(a);
                for (;j>=0;j--)
                    list.remove(j);

                list.add(a);
                tmp=list.size();
            }
        }
        if(tmp>result)
            result=tmp;
        //System.out.println(a);
        return result;
    }

拓展

串操作卧抗，與此類似還需要一個變量來記錄每一此操作的狀態(tài)值鳖粟，并且在恰當結(jié)果下更新結(jié)果的情況社裆，如：求一串數(shù)字的最大字串和向图。其最簡單的代碼如下（還可以考慮如果輸入很大的時候需要用字符串或者字符串數(shù)組的情況）：

public long maxSum(int[] a){
    int len=a.length;
    long tmp=0;
    long result=0;
    int i=0;
    //排除前面的非正數(shù)
    while(a[i]>=0)
    {
        i++;
    }
    //當輸入全部為非正數(shù)的情況
    if(i==length)
    {
        
        for(int j=1;j<len;j++)
        {
            if(result<a[j])
                result=a[j];
        }   
        return result;
    }else{
        result=a[i];
        while(i<length){
            tmp=a[i]+tmp;
            if(result<tmp){
                result=tmp;
            }else{
                if(tmp<0){
                    tmp=0;
                }
            }
            i++;
        }
    }
    return result;
}