Three Number Sum

Write a function that takes in a non-empty array of distinct integers and an integer representing a target sum. The function should find all triplets in the array that sum up to the target sum and return a two-dimensional array of all these triplets. The numbers in each triplet should be ordered in ascending order, and the triplets themselves should be ordered in ascending order with respect to the numbers they hold.

If no three numbers sum up to the target sum, the function should return an empty array.

 

Time complexity: O(n^2)

Space complexity: O(n)

public static List<Integer[]> threeNumberSum(int[] array, int targetSum) {
    int size = array.length;

    List<Integer[]> answers = new ArrayList<>();

    if (size < 2) {
        return answers;
    }

    Arrays.sort(array);

    for (int x = 0; x < size - 2; x++) {
        int left = x + 1;
        int right = size - 1;

        while (left < right) {
            int sum = array[x] + array[left] + array[right];

            if (sum == targetSum) {
                Integer[] triplet = {array[x], array[left], array[right]};
                answers.add(triplet);

                left++;
                right--;

            } else if (sum < targetSum) {

                left++;

            } else if (sum > targetSum) {

                right--;

            }
        }
    }

    return answers;
}

 




Subscribe To Our Newsletter
You will receive our latest post and tutorial.
Thank you for subscribing!

required
required


Leave a Reply

Your email address will not be published.