LeetCode - Algorithms - 15. 3Sum

Beats me! Just post solution of other guy.

Problem

15. 3Sum

Java

two pointers

© LeetCode – 3Sum - two pointers

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);

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

        for (int i = 0; i < nums.length; i++) {
            int j = i + 1;
            int k = nums.length - 1;

            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            while (j < k) {
                if (k < nums.length - 1 && nums[k] == nums[k + 1]) {
                    k--;
                    continue;
                }

                if (nums[i] + nums[j] + nums[k] > 0) {
                    k--;
                } else if (nums[i] + nums[j] + nums[k] < 0) {
                    j++;
                } else {
                    ArrayList<Integer> l = new ArrayList<>();
                    l.add(nums[i]);
                    l.add(nums[j]);
                    l.add(nums[k]);
                    result.add(l);
                    j++;
                    k--;
                }
            }
        }

        return result;
    }
}

Submission Detail

• 318 / 318 test cases passed.
• Runtime: 21 ms, faster than 65.13% of Java online submissions for 3Sum.
• Memory Usage: 43.1 MB, less than 88.54% of Java online submissions for 3Sum.

Quadratic algorithm

© 3SUM - Quadratic algorithm

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        final int N = nums.length;
        Arrays.sort(nums);
        Set<List<Integer>> set = new HashSet<List<Integer>>();
        int start, end;
        int a, b, c;
        for (int i = 0; i < N - 1; i++) {
            a = nums[i];
            start = i + 1;
            end = N - 1;
            while (start < end) {
                b = nums[start];
                c = nums[end];
                if (a + b + c == 0) {
                    set.add(new ArrayList<>(Arrays.asList(a, b, c)));
                    start = start + 1;
                    end = end - 1;
                } else if (a + b + c > 0) {
                    end = end - 1;
                } else {
                    start = start + 1;
                }
            }
        }
        return new ArrayList<>(set);
    }
}

Submission Detail

• 318 / 318 test cases passed.
• Runtime: 230 ms, faster than 27.64% of Java online submissions for 3Sum.
• Memory Usage: 43.5 MB, less than 64.19% of Java online submissions for 3Sum.

concise solution

© Java clean solution (15 lines) https://leetcode.com/problems/3sum/discuss/865345/Java-clean-solution-(15-lines)

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        HashSet<List<Integer>> res = new HashSet<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            int target = -1 * nums[i];
            HashSet<Integer> set = new HashSet<>();
            for (int j = i + 1; j < nums.length; j++) {
                if (set.contains(target - nums[j]))
                    res.add(new ArrayList<>(Arrays.asList(nums[i], nums[j], target - nums[j])));
                set.add(nums[j]);
            }
        }
        return new ArrayList<>(res);
    }
}

Submission Detail

• 318 / 318 test cases passed.
• Runtime: 768 ms, faster than 6.51% of Java online submissions for 3Sum.
• Memory Usage: 43.4 MB, less than 73.80% of Java online submissions for 3Sum.

ref

• 3SUM