My accepted solution O(n^2), run time 548ms, could I do any better


  • 1
    W
    public List<List<Integer>> threeSum(int[] num) {
        if (num == null || num.length < 3) {
            return new ArrayList();
        }
    
        ArrayList<List<Integer>> triplets = new ArrayList<List<Integer>>();
    
        Arrays.sort(num);
        int a = 0, b = 1, c = num.length - 1;
        int sum = 0;
        while (a < num.length - 2) {
            // remove duplicate
            if (a > 0 && num[a] == num[a-1]) {
                a++;
                continue;
            }
            b = a + 1;
            c = num.length - 1;
            while (b < c) {
                // remove duplicate
                if (b > a + 1 && num[b] == num[b-1]) {
                    b++;
                    continue;
                }
                // remove duplicate
                if (c < num.length -1 && num[c] == num[c+1]) {
                    c--;
                    continue;
                }
    
                sum = num[a] + num[b] + num[c];
                if (sum < 0) {
                    b++;
                } else if (sum > 0) {
                    c--;
                } else {
                    ArrayList<Integer> triplet = new ArrayList<Integer>();
                    triplet.add(num[a]);
                    triplet.add(num[b]);
                    triplet.add(num[c]);
                    triplets.add(triplet);
                    b++; c--;
    
                }
            }
            a++;
        }
        return triplets;
    }
    

    run time is a lot slower than similar solutions in c++, which 212ms, wondering why?


  • 0
    Z

    could your code hand some case like [-1 -1 -1 0 0 0 2 2], one solution would be [0 0 0].
    can this solution be found?


  • 1
    D

    Java is supposed to be running much slower than c++. It's normal.


Log in to reply
 

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