package Leetcode.TwoPointer;

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

/**
 * @author zhengstars
 * @date 2024/02/27
 */
public class ThreeSum {
    // The threeSum method which finds all triplets in the given array that sums to zero.
    public static List<List<Integer>> threeSum(int[] nums) {
        // Sort the array.
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        // Loop through the array.
        for(int i = 0; i < nums.length; i++){
            // Skip over duplicates.
            if(i > 0 && nums[i] == nums[i-1]){
                continue;
            }
            // Initiate two pointers j and k.
            int k = nums.length - 1;
            // We want to find two numbers whose sum equals to -nums[i].
            int target = -nums[i];
            // Loop through the rest of the array.
            for(int j = i + 1; j < nums.length; j++){
                // Skip over duplicates.
                if(j > i + 1 && nums[j] == nums[j-1]){
                    continue;
                }
                // Decrease k until the sum of nums[j] and nums[k] is less than or equals to target.
                while(j < k && nums[j] + nums[k] > target){
                    k--;
                }
                // If j equals to k, we break the loop since k cannot be less than j.
                if(j == k){
                    break;
                }
                // If the sum of nums[j] and nums[k] equals to target.
                if(nums[j] + nums[k] == target){
                    // Add {nums[i], nums[j], nums[k]} to ans.
                    List<Integer> list = new ArrayList<Integer>();
                    list.add(nums[i]);
                    list.add(nums[j]);
                    list.add(nums[k]);
                    ans.add(list);
                }
            }
        }
        // Return all found triplets.
        return ans;
    }

    public static void main(String[] args) {
        // Test case 1: an input with multiple different triplets.
        int[] nums1 = {-1,0,1,2,-1,-4};
        System.out.println("Test case 1 result: " + threeSum(nums1)); // Output: [[-1, -1, 2], [-1, 0, 1]]

        // Test case 2: an input with no valid triplet.
        int[] nums2 = {0,1,1};
        System.out.println("Test case 2 result: " + threeSum(nums2)); // Output: []

        // Test case 3: an input with three identical numbers.
        int[] nums3 = {0,0,0};
        System.out.println("Test case 3 result: " + threeSum(nums3)); // Output: [[0, 0, 0]]
    }
}