LeetCode. 15. 3Sum

[Link] https://leetcode.com/problems/3sum/

Approach

Sort the array, then fix each index i in turn and search the suffix with two pointers, left = i + 1 and right = nums.length - 1. The sorted order lets the pointers move monotonically: if the three-value sum is below zero, every pair using the current left and a smaller right endpoint is also too small, so advancing left is safe. If the sum is above zero, every pair using the current right and a larger left endpoint is also too large, so decrementing right is safe. On a zero sum, record the triplet and move both pointers.

Skip an index when its value matches the previous fixed value, so the same first value is not searched again. After recording a triplet, skip repeated values at both pointers before continuing; this prevents producing the same value triplet more than once. Since the array is sorted, once nums[i] > 0, all later values are positive too and the search can stop.

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

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

        for (int i = 0; i < nums.length - 2; i++) {
            if (nums[i] > 0) {
                break;
            }
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            int left = i + 1;
            int right = nums.length - 1;
            while (left < right) {
                long sum = (long) nums[i] + nums[left] + nums[right];
                if (sum < 0) {
                    left++;
                } else if (sum > 0) {
                    right--;
                } else {
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    while (left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }
                    while (left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }
                    left++;
                    right--;
                }
            }
        }
        return result;
    }
}

Sorting takes O(N log N) time and the fixed-index two-pointer searches take O(N²) time overall. Sorting is in place; its implementation uses O(log N) workspace. The returned triplets require O(K) output space, where K is the number of triplets.