Easiest Java Solution


  • 90

    Sort the array, iterate through the list, and use another two pointers to approach the target.

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

  • 1
    C

    Hi there, thank you for providing such clean and efficient code. I have a question regarding first line. When I use List<List<Integer>> result = new ArrayList<List<Integer>>(), TLE happens and that's the only thing I changed from your code! Do you know what happened?


  • 4

    Hi, thanks for your question! I guess you are returning List<List<Integer>>. You can either use

    List<List<Integer>> result = new ArrayList<List<Integer>>();
    

    or use type inference

    List<List<Integer>> result = new ArrayList<>();
    

    Your change might not be the right syntax.


  • 0
    C

    Actually I'm using the first syntax you provided and it keeps TLE.


  • 0

    Hi @dqf1992, I tried that and I was able to being accepted. Maybe you have something incorrect in the middle.


  • 0
    Y

    smart code to skip duplicates


  • 0

    @yanggao Thanks :)


  • 0
    T

    I have the same problem as you,but I find I don't code this sentence "j++; k--;"


  • 0
    F

    "Skip the same result " is so important...


  • 0
    P

    I am wondering about the time complexity.
    Sorting the input is n log(n)
    Looping on each other two elements is n^2
    Should not the overall complexity be n^2 + n log(n)?


  • 0
    F

    that's very smart


  • 0
    H

    @yanggao I think so


  • 0
    A

    i dont know why first step is sort the array,is this only prevent duplicate?can someone explain to me,sorry for my english,thanks


  • 0
    L

    @asafapowellyb Yes. If you don't skip then you will need to use a set to store the triplets somehow. It works together with the while loop to skip duplicates once you find a match when nums[j]+nums[k]==target.


  • 0
    S

    @yavinci nice answer.

    I wonder if anyone could explain here, why, while the elements of the triple ALWAYS 'skip' the replicate (the 'continue'), the last two elements (marked by 'low' and 'high') ONLY do the 'skipping' when we found a valid triple?

    Thanks!


  • 0
    Y

    @pep.o
    n^2 is much bigger than nlogn when n --> infinite.
    Similarly, suppose step 1 uses nlogn and step 2 uses n, the overall time cost will be nlogn.


  • 0
    A

    @pep.o O(n^2) trumps O(nlogn) so the overall complexity becomes n^2


  • 0
    C
    This post is deleted!

  • 0
    M
    } else if (nums[j] + nums[k] > target) {
         k--;
    } else {
         j++;
    }
    

    Can someone please explain this part? So if you're over the target you move the right index (k) down, but if you're under the target you move the left index (j) up. I don't understand.


  • 0
    K

    @marty7044 Since the array is sorted, we are decreasing the sum by moving k downards. If the sum is too small, we need to increase the sum by moving j forwards. k and j represent the bounds of the pointers, so you can't get larger than k, and you can't get smaller than j.


Log in to reply
 

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