3Sum

1package pkg5leetcode.blind75;2 3/*4 * 3Sum | LC 155 * APPROACH: Sort, fix i, two-pointer scan for triplets summing to zero.6 * COMPLEXITY: Time O(n^2), Space O(1) excluding output7 */8import java.util.*;9 10public class blind75_LC15ThreeSum {11    static List<List<Integer>> threeSum(int[] nums) {12        Arrays.sort(nums);13        List<List<Integer>> res = new ArrayList<>();14        for (int i = 0; i < nums.length; i++) {15            if (i > 0 && nums[i] == nums[i - 1]) continue;16            int lo = i + 1, hi = nums.length - 1;17            while (lo < hi) {18                int sum = nums[i] + nums[lo] + nums[hi];19                if (sum == 0) {20                    res.add(Arrays.asList(nums[i], nums[lo], nums[hi]));21                    lo++; hi--;22                    while (lo < hi && nums[lo] == nums[lo - 1]) lo++;23                    while (lo < hi && nums[hi] == nums[hi + 1]) hi--;24                } else if (sum < 0) lo++;25                else hi--;26            }27        }28        return res;29    }30 31    public static void main(String[] args) {32        List<List<Integer>> r = threeSum(new int[]{-1, 0, 1, 2, -1, -4});33        check(r.size() == 2, "size");34        check(r.contains(Arrays.asList(-1, -1, 2)), "triplet1");35        check(r.contains(Arrays.asList(-1, 0, 1)), "triplet2");36        System.out.println("all tests passed");37    }38 39    static void check(boolean cond, String name) {40        if (!cond) throw new AssertionError("FAILED: " + name);41        System.out.println("  PASS " + name);42    }43}