[LeetCode] 3Sum (Java)

Problem

Solution

Two-Pointer (st, ed)

1. First, sort the array in ascending order.

 - In order for the sum of three numbers to be zero, at least one of the numbers must be negative.
   (excluding the case where all three are zero)

 - To simplify calculations, sort the array in ascending order first.

 

2. Set the pivot point (i) and two pointers (st, ed) in the sorted array.
- The pivot point (i) can range from the smallest number in the sorted array to the third largest number.
  (since st, ed can occupy the last two positions)
- st points to the number immediately after the pivot, and ed starts from the largest number in the array.

 

3. Compare the sum of the number at the pivot point (i) with the numbers at st and ed.
 - If the sum is 0, add it to the result array.
   Then, move the pointers until different numbers are encountered at each st and ed position. (st++, ed--)
 - If the sum is greater than 0, it means the number added is too large, so decrement ed.
 - If the sum is less than 0, it means the number added is too small, so increment st.

 

4. Exclude duplicate triplets by skipping computation if the pivot point (i) has the same value as the previous pivot point (i-1).

 

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        
        List<List<Integer>> ans = new ArrayList<>();

        Arrays.sort(nums);

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

            int st = i + 1;
            int ed = nums.length - 1;

            while (st < ed) {
                int sum = nums[i] + nums[st] + nums[ed];
                
                if (sum == 0) {
                    ans.add(Arrays.asList(nums[i], nums[st++], nums[ed--]));
                    while(nums[st] == nums[st - 1] && st < ed) st++;
                    while(nums[ed] == nums[ed + 1] && st < ed) ed--;
                } else if (sum > 0) {
                    ed--;
                } else {
                    st++;
                }
            }
        }

        return ans;
    }
}