Three sum

Given an array return 3Sum of elements of the array equal to target

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0 Notice that the solution set must not contain duplicate triplets

1. Brute force approach : complexity n^3
2. Optimized solution : complexity n^2

Appoach

1. start with first loop till n-1, start element is the element at index i
2. Next we need to find the two elements whose sum == target-i
3. keep 2 pointers, left and right (left starts from i+1 and right moves back to right-1)
4. do a total sum, if the total sum == taget then print the triplets

Print uniqiue triplets ???? Sort the array, if i-1 and i are equal then just keep moving forward

private List threeSum(int [] input, int target) {
        List<int[]> list = new ArrayList<>();
        if(input == null || input.length == 0) {
            list.add(new int[]{});
            return list;
        }
        Arrays.sort(input);
        int length = input.length - 1 ;
        for (int i=0; i < length ; i++ ) {
            int start = input[i];
            int leftSum = target - input[i];
            int left = i + 1;
            int right = length;
            while (left < right) {
                int currentSum = input[left] + input[right];
                if(currentSum == leftSum) {
                    while (input[left] == input[left-1] ) {
                        ++left;     //ensure no duplicates
                    }
                    list.add(new int[]{start, input[left], input[right]});
                    left = left +1;
                    right = right -1;
                   
                } else if(currentSum > leftSum) {
                    right = right - 1;
                } else {
                    left = left + 1;
                }
            }
        }
        return list;
    }