Problem3

题目： 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.

题目提炼

计算给定字符串的不含有重复元素的字串的最大长度。

分析

首先这应该是一道与串相关的算法题，这里只要求返回最大长度，那么肯定会有一个变量tmp记录每一次更新后，当前满足条件的字串的长度。还有一个变量result用来记录当前满足条件的字串的最大长度，每次操作后，都需要比较tmp与result的大小进而更新result。还需要一个集合来对已经读取的字符进行缓存，这里有一个值得注意的地方：当发现缓存的字符集包含了当前读取的字符时，可以将字符集中第一个字符到重复字符的部分截取，再将当前字符加入字符集中。出于这一特性，可以使用list作为缓存字符集的容器，这里在代码是线上有一个优化，就是将当前读取的字符是否与已读字符重复作为result更新的条件，然后在循环结束后再比较一次，防止循环中一次更新都没有做的情况。这样不用每次循环都去比较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;
    }

拓展

串操作，与此类似还需要一个变量来记录每一此操作的状态值，并且在恰当结果下更新结果的情况，如：求一串数字的最大字串和。其最简单的代码如下（还可以考虑如果输入很大的时候需要用字符串或者字符串数组的情况）：

public long maxSum(int[] a){
    int len=a.length;
    long tmp=0;
    long result=0;
    int i=0;
    //排除前面的非正数
    while(a[i]>=0)
    {
        i++;
    }
    //当输入全部为非正数的情况
    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;
}