My accepted O(n^2) solution without hashmap


  • 14
    U
    public class Solution {
        
        int a, b, c;
        List<List<Integer>> result = new ArrayList();
    
        public List<List<Integer>> threeSum(int[] num) {
            Arrays.sort(num);
            
            for (int i = 0 ; i <= num.length - 3; i++) {
                a = num[i];
                for (int j = i+1, k = num.length - 1; j < k;) {
                    b = num[j];
                    c = num[k];
                    if (b + c == -1*a) {
                        List list = new ArrayList<Integer>();
                        list.add(a);
                        list.add(b);
                        list.add(c);
                        result.add(list);
                        j++;
                        k--;
                    } else if (b + c < -1*a) {
                        j++;
                    } else {
                        k--;
                    }
                }
            }
            
            // remove duplicated items.
            for (int i = result.size() - 1; i >= 1; i--) {
                for (int j = i-1; j >= 0; j--) {
                    if (result.get(i).get(0) == result.get(j).get(0)
                        && result.get(i).get(1) == result.get(j).get(1)
                        && result.get(i).get(2) == result.get(j).get(2)) {
                        result.remove(j);
                        i--;
                    }
                }
            }
            return result;
        }
    
    }

  • 0
    S

    Thanks for your post. However it would be better to share solution with correct code format and elaborated thoughts. Please read the Discuss FAQ for more info. Take a look at good sharing example

    Pay attention to "Writing code? Select all code then click on the {} button to preserve code formatting.” above text editor.


  • 0
    B

    Not a java programmer, but does a java list provide constant time random access? If not, is the remove duplicate step really O(n^2)?
    Either way, you can actually get rid of the additional step to remove duplicate items. Since you have already sorted the input, elements that are equal would be next to each other. You can skip all but one of such equal elements when performing the 3sum check.


  • 0
    U

    Yes, so I use ArrayList which can access the items in O(1) time complexity, if using LinkedList, I will get TLE.


  • 0
    B

    You can still get rid of the additional step to remove duplicates, as an optimization.


  • 0
    L

    Mine detects duplicate in-place.

    /**
     * Algorithm is O(n^2) without using extra space except to store the solution.
     */
    #include<iostream>
    #include<vector>
    #include<algorithm>
    using namespace std;
    
    struct comp{
        inline bool operator()(const int&a, const int&b)const{
            return a<b;
        }
    };
    
    class Solution {
    public:
        vector<vector<int> > threeSum(vector<int> &num) {
            int i,j;
            sort(num.begin(),num.end(),comp());
            vector<vector<int> > ans;
            int prev1;
            const int n=num.size();
            for(i=0;i<n;prev1=num[i],i++){
                int a=num[i];
                // skip duplicates to avoid duplicate triplets.
                if(i&&a==prev1)continue;
                // below is essentially the O(n) method for 2sum,
                // with duplicate detection.
                int i1=i+1,i2=n-1,prev2,prev3=num[i2]+1;
                while(i1<i2){
                    int b=num[i1],c=num[i2],sum=a+b+c;
                    if(sum>0)i2--;
                    else if(sum<0)i1++;
                    else {
                        if (b!=prev2||c!=prev3){
                            ans.emplace_back();
                            ans.back()={a,b,c};
                        }
                        i1++;
                    }
                    prev2=b;
                    prev3=c;
                }
            }
            return ans;
        }
    };
    

  • 0
    L

    note that ArrayList.remove is not O(1)


  • 32
    P

    Here is my code using cpp, also do not use hashmap and without deleting duplicates

    vector<vector<int> > threeSum(vector<int> &num) {
        vector<vector<int> > res;
        if (num.size() <= 2) return res;
        sort(num.begin(), num.end());
        int twoSum;
        for (int i = 0; i < num.size() - 2;)
        {
            int l = i + 1, r = num.size() - 1;
            twoSum = 0 - num[i];
            while (l < r)
            {
                if (num[l] + num[r] < twoSum) l++;
                else if (num[l] + num[r] == twoSum)
                {
                    vector<int> three(3);
                    three[0] = num[i];
                    three[1] = num[l];
                    three[2] = num[r];
                    res.push_back(three);
                    do { l++; }while (l < r && num[l - 1] == num[l]);
                    do { r--; }while (l < r && num[r + 1] == num[r]);
                }
                else r--;
            }
            do{ i++; }while (i < num.size() - 1 && num[i - 1] == num[i]);
        }
        sort(res.begin(),res.end());
        return res;
    }

  • 0
    Z

    deleted comm


  • 20
    Z

    My Java solution. You don't need to remove duplicate items.

    public class Solution {
        public List<List<Integer>> threeSum(int[] num) {
            Arrays.sort(num);
            List<List<Integer>> result = new ArrayList<List<Integer>>();
    
            for(int i = 0; i < num.length-2; ++i) {
                if(i > 0 && num[i] == num[i-1])
                    continue;
    
                int j = i + 1, k = num.length-1;
    
                while(j < k) {
                    int candidate = num[i] + num[j] + num[k];
                    if(candidate <= 0) {
                        if(candidate == 0)
                            result.add(Arrays.asList(num[i],num[j], num[k]));
                        ++j;
                        while (j < k && num[j] == num[j-1])
                            ++j;
                    }
                    else if(candidate > 0) {
                        --k;
                        while (k > j && num[k] == num[k+1])
                            --k;
                    }
                }
            }
    
            return result;
        }
    }

  • 0
    L

    Brilliant. This left-right-scan-way.


  • 0
    J

    My recursive solution inspired by “Subsets”:

    class Solution {
    public:
        vector<vector<int>> threeSum(vector<int> &num) {
            vector<vector<int>> result;
            if (num.size() < 3) return result;
            sort(num.begin(), num.end());  // dirty
            vector<int> subset;
            collectSets(num, 0, subset, result);
            return result;
        }
        void collectSets(vector<int> &numbers, int n, vector<int> &subset, vector<vector<int>> &result) {
            int sum = accumulate(subset.begin(), subset.end(), 0);
            if (sum > 0) return;
            switch (subset.size()) {
            case 3:
                if (sum == 0) result.push_back(subset);
                return;
            case 2:
                if (sum + numbers.back() < 0) return;
                break;
            case 1:
                if (sum + numbers.back() + numbers[numbers.size()-2] < 0) return;
                break;
            }
            for (int i = n; i < numbers.size(); i++) {
                subset.push_back(numbers[i]);
                collectSets(numbers, i+1, subset, result);
                subset.pop_back();
                while (i < numbers.size()-1 && numbers[i] == numbers[i+1]) i++;
            }
        }
    };
    

    Though not very fast. :P


  • 0
    D

    hi, I meet a strange question. Can you help me ? i user nearly the same code with you, but this:

    vector<int> tmp(3) ;
    tmp.push_back(num[i]);
    tmp.push_back(num[l]);
    tmp.push_back(num[h]);

    I receive a Output Limit Exceeded error. How does it come ?


  • 2
    E

    Did a little modification to this code. A little bit faster since no need to remove the duplicate.

    public class Solution {
    public List<List<Integer>> threeSum(int[] num) {
        int a, b, c;
        HashSet<List<Integer>> result = new HashSet();
        Arrays.sort(num);
    
        for (int i = 0 ; i <= num.length - 3; i++) {
            a = num[i];
            for (int j = i+1, k = num.length - 1; j < k;) {
                b = num[j];
                c = num[k];
                if (b + c == -1*a) {
                    List list = new ArrayList<Integer>();
                    list.add(a);
                    list.add(b);
                    list.add(c);
                    result.add(list);
                    j++;
                    k--;
                } else if (b + c < -1*a) {
                    j++;
                } else {
                    k--;
                }
            }
        }
        List<List<Integer>> listresult= new ArrayList(result); 
        return listresult;
    }
    

  • 0
    Z

  • 0
    M

    push_back () means you add data after the 3 node you initialized.by doing this, the size of tmp is 6


  • 0
    D

    wow,I got it. thanks very much!


  • 0
    Z

    Pretty nice solution! But could you please explain about why you use postfix instead of prefix? Even it doesn't matter with the answer... Thank you!


  • 0
    Z

    You mean that I use the prefix operator "++i" instead of the post-fix operator "i++"?
    The difference between the two:

    int a = 5, b = 5;

    int c = a++;

    int d = ++b;

    System.out.println("c = " + с);

    System.out.println("d = " + d);

    Output:

    c = 5

    d = 6

    That means that the prefix operator increments variable it is applied to and only after returns the value,
    but the post-fix operator increments variable and returns its original value.
    When you don't have a variable you assign the result to it doesn't matter which one you use.
    But I think using prefix operator in such cases is less error-prone because if you refactor
    your code to start using returned value it might cause bugs.


  • 0
    L

    Nice solution. But I am not quite sure why should add "i>0" in
    if(i > 0 && num[i] == num[i-1])
    continue;
    i should always be larger than zero, right?


Log in to reply
 

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