Concise O(N^2) Java solution


  • 330
    S

    Hi guys!

    The idea is to sort an input array and then run through all indices of a possible first element of a triplet. For each possible first element we make a standard bi-directional 2Sum sweep of the remaining part of the array. Also we want to skip equal elements to avoid duplicates in the answer without making a set or smth like that.

    public List<List<Integer>> threeSum(int[] num) {
        Arrays.sort(num);
        List<List<Integer>> res = new LinkedList<>(); 
        for (int i = 0; i < num.length-2; i++) {
            if (i == 0 || (i > 0 && num[i] != num[i-1])) {
                int lo = i+1, hi = num.length-1, sum = 0 - num[i];
                while (lo < hi) {
                    if (num[lo] + num[hi] == sum) {
                        res.add(Arrays.asList(num[i], num[lo], num[hi]));
                        while (lo < hi && num[lo] == num[lo+1]) lo++;
                        while (lo < hi && num[hi] == num[hi-1]) hi--;
                        lo++; hi--;
                    } else if (num[lo] + num[hi] < sum) lo++;
                    else hi--;
               }
            }
        }
        return res;
    }
    

    Have a nice coding!


  • 2
    R

    the trick that avoid using Set is hard to understand, however faster indeed! so +1


  • 0
    S

    Really concise!


  • 2
    U

    excellent solution


  • 9
    C

    Hi, I have exactly the same idea as yours. Just use c++

    class Solution {
    public:
        vector<vector<int> > threeSum(vector<int> &num) {
            vector<vector<int> > ans;
            int i, j, k, n = num.size();
            sort(num.begin(), num.begin() + n);
            for (i = 0; i < n; i++){
                if (i > 0 && num[i] == num[i - 1]) continue;
                k = n - 1;
                j = i + 1;
                while (j < k){
                    if (num[i] + num[j] + num[k] > 0) k--;
                    else if (num[i] + num[j] + num[k] < 0) j++;
                    else{
                        vector<int> tmp;
                        tmp.push_back(num[i]);
                        tmp.push_back(num[j]);
                        tmp.push_back(num[k]);
                        ans.push_back(tmp);
                        while (j < k && num[k] == num[k - 1]) k--;
                        while (j < k && num[j] == num[j + 1]) j++;
                        k--; j++;
                    }
                }
            }
            return ans;
        }
    };
    

  • 0
    B
    This post is deleted!

  • 42
    S

    I think, maybe we can improve this solution a little bit.
    See comment in below code.

    public List<List<Integer>> threeSum(int[] num) {
        Arrays.sort(num);
        List<List<Integer>> res = new LinkedList<>(); 
        for (int i = 0; i < num.length-2; i++) {
            if (i == 0 || (i > 0 && num[i] != num[i-1])) {
                int lo = i+1, hi = num.length-1, sum = 0 - num[i];
                while (lo < hi) {
                    if (num[lo] + num[hi] == sum) {
                        res.add(Arrays.asList(num[i], num[lo], num[hi]));
                        while (lo < hi && num[lo] == num[lo+1]) lo++;
                        while (lo < hi && num[hi] == num[hi-1]) hi--;
                        lo++; hi--;
                    } else if (num[lo] + num[hi] < sum) {
                        // improve: skip duplicates
                        while (lo < hi && num[lo] == num[lo+1]) lo++;
                        lo++;
                    } else {
                        // improve: skip duplicates
                        while (lo < hi && num[hi] == num[hi-1]) hi--;
                        hi--;
                    }
                }
            }
        }
        return res;
    }
    

  • 1
    T

    this is really good solution. Thanks a lot.


  • 1

    Thanks to all of your solutions, I have gathered and made a more compact and efficient solution. Thanks guys, StevenCooks and shpolsky.

    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> r = new LinkedList<>(); 
        for (int i=0; i<nums.length-2; i++)
            if (i==0 || (i>0 && nums[i]!=nums[i-1])) {
                int j = i+1, k = nums.length-1, sum = -nums[i];
                while (j < k) {
                    if (j!=i+1 && nums[j]==nums[j-1]) j++;
                    else if (k!=nums.length-1 && nums[k]==nums[k+1]) k--;
                    else if (nums[j] + nums[k] == sum) {
                        r.add(Arrays.asList(nums[i], nums[j], nums[k]));
                        while (j < k && nums[j] == nums[j+1]) j++;
                        while (j < k && nums[k] == nums[k-1]) k--;
                        j++; k--;
                    } else if (nums[j] + nums[k] < sum) j++;
                    else k--;
                }
            }
        return r;
    }

  • 21
    Z

    A trick to improve performance: once nums[i] > 0, then break.
    Since the nums is sorted, if first number is bigger than 0, it is impossible to have a sum of 0.


  • 1
    Z

    This actually slows down performance if there are not a lot of duplicates in nums. Then comparisons such as (lo < hi && num[lo] == num[lo+1]) and (lo < hi && num[hi] == num[hi-1]) are a waste of time.


  • 0
    L

    when i == 0, why does it not throw PointerOutOfRange exception? You used num[i-1];


  • 1
    M

    if (i == 0 || (i > 0 && num[i] != num[i-1]))
    Here if i == 0 is true, we don't need to test the second condition because we use "||".


  • 5
    T

    Thank you! Just using python.

        def threeSum(self, nums):
            """
            :type nums: List[int]
            :rtype: List[List[int]]
            """
            nums.sort()
            res = []
            for i in xrange(len(nums)):
                if i != 0 and nums[i] == nums[i-1]: continue
                target = -nums[i]
                l, r = i+1, len(nums)-1
                while l < r:
                    if nums[l] + nums[r] == target:
                        res.append((nums[i], nums[l], nums[r]))
                        while l < r and nums[l] == nums[l+1]: l += 1
                        while l < r and nums[r] == nums[r-1]: r -= 1
                        l += 1
                        r -= 1
                    elif nums[l] + nums[r] < target:
                        l += 1
                    else:
                        r -= 1
            return res

  • 0
    S
    This post is deleted!

  • 3
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> list = new ArrayList<List<Integer>>();
        for(int i = 0; i < nums.length; i++) {
            if(i > 0 && (nums[i] == nums[i-1])) continue; // avoid duplicates
            for(int j = i+1, k = nums.length-1; j<k;) {
                if(nums[i] + nums[j] + nums[k] == 0) {
                    list.add(Arrays.asList(nums[i],nums[j],nums[k]));
                    j++;k--;
                    while((j < k) && (nums[j] == nums[j-1]))j++;// avoid duplicates
                    while((j < k) && (nums[k] == nums[k+1]))k--;// avoid duplicates
                }else if(nums[i] + nums[j] + nums[k] > 0) k--;
                else j++;
            }
        }
        return list;
    }

  • 0

    that really help~


  • 0
    H
    This post is deleted!

  • 6
    R

    Based on your solution, I have a optimization:
    for the traverse of nums[i], it's not necessary for those positive numbers.

    public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList();
        if(nums.length<3) return res;
        Arrays.sort(nums);
        for(int i = 0; i<nums.length-2; i++){
            if(nums[i]>0) break;
            if(i==0||(i>0)&&(nums[i]!=nums[i-1])){
                int lo=i+1,hi=nums.length-1, sum=0-nums[i];
                while(lo<hi){
                    if(nums[lo]+nums[hi]==sum){
                        res.add(Arrays.asList(nums[i],nums[lo],nums[hi]));
                        while(lo<hi&&nums[lo]==nums[lo+1]) lo++;
                        while(lo<hi&&nums[hi]==nums[hi-1]) hi--;
                        lo++;
                        hi--;
                    }
                    else if(nums[lo]+nums[hi]<sum) lo++;
                    else hi--;
                }                    
            }
        }
        return res;
    }
    

    }


  • 1
    D

    @shpolsky So the only purpose for sorting beforehand is for handling duplicated numbers. If this question only has distinct numbers, then no need for sorting beforehand.


Log in to reply
 

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