TLE but it's O(n^2), please help me improve it! Thank you!

  • 0
    public static List<List<Integer>> threeSum(int[] sum){
            List<List<Integer>> result = new ArrayList<List<Integer>>();
            if (sum.length <3) return result;
            HashMap<Integer, Single> singles = new HashMap<Integer, Single>();
            for (int i = 0; i< sum.length; i++){
                singles.put(sum[i], new Single(sum[i],i));
            ArrayList<Pair> pairs = new ArrayList<Pair>();
            for (int i = 0; i<sum.length; i++){
                for (int j = i+1; j<sum.length; j++){
                    pairs.add(new Pair(sum[i], i, sum[j], j));
            for (Pair pair: pairs){
                Single single = singles.get(0-pair.getSum());
                if (single != null && pair.compareIndex(single.getIndex())){
                    ArrayList<Integer> triplet = new ArrayList<Integer>();
                    if (!result.contains(triplet)) result.add(triplet);
            return result;
    class Pair {
        int a;
        int aIndex;
        int b;
        int bIndex;
        int sum;
        public Pair(int a, int ai, int b, int bi) {
            this.a = a;
            this.aIndex = ai;
            this.b = b;
            this.bIndex = bi;
            this.sum = a+b;
        public boolean compareIndex(int index){
            return aIndex!=index && bIndex!=index;
        public int getFirst(){
            return a;
        public int getFirstIndex(){
            return aIndex;
        public int getSecond(){
            return b;
        public int getSecondIndex(){
            return bIndex;
        public int getSum(){
            return sum;
    class Single {
        private int value;
        private int index;
        public Single(int v, int i){
            this.value = v;
            this.index = i;
        public int getValue(){
            return value;
        public int getIndex(){
            return index;

  • 0

    Hello!,you should check your index j and index i,for more details, Please click the URL:

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.