（算法）去除字符串中的重复字符（时间复杂度）

1.一般会想到遍历字符串，去除重复的字符，这样时间复杂度是O(n²)，时间复杂度太高。

static String sub(String str){

StringBuffer result =newStringBuffer();

List list =new ArrayList();

char[] cs = str.toCharArray();

for(int i=0; i<cs.length; i++){

if(!list.contains(cs[i])){

result.append(cs[i]);

list.add(cs[i]);

}

}

returnresult.toString();

}

2.再仔细想一想

用java的String的indexOf方法来达到字符串去重的目的，indexOf的功能是返回指定字符在此字符串中第一次出现处的索引：

public static String QuChong(String str){

        StringBuilder sb=new StringBuilder();

        for(int i=0;i<str.length();i++){

            if(str.indexOf(str.charAt(i))==i){

                //第一次出现

                sb.append(str.charAt(i));

            }

        }

        String result=sb.toString();

        return result;

    }