3Sum

LeetCode https://leetcode.cn/problems/3sum/

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> results = new ArrayList<>();
        if (nums == null || nums.length < 3) {
            return results;
        }

        Arrays.sort(nums);

        for (int i = 0; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int start = i + 1;
            int end = nums.length - 1;
            int diff = 0 - nums[i];
            while (start < end) {
                int current2Sum = nums[start] + nums[end];
                if (current2Sum == diff) {
                    results.add(new ArrayList<>(Arrays.asList(nums[i], nums[start], nums[end])));
                    while (start < nums.length - 1 && nums[start] == nums[start + 1]) {
                        start++;
                    }
                    start++;
                } else if (current2Sum < diff) {
                    while (start < nums.length - 1 && nums[start] == nums[start + 1]) {
                        start++;
                    }
                    start++;
                } else {
                    while (end > 0 && nums[end] == nums[end - 1]) {
                        end--;
                    }
                    end--;
                }
            }
        }
        
        return results;
    }
}

Complexity

• Time = O($n^2$)
• Space = O(1)