From arbitrary integers,find pairs that sum to expected sum, return array results as collection

Question

Interview Question at large company: How would you solve?

Given a list of arbitrary integers, find the pairs of integers that sum to an unknown expected sum. Return the array results in a collection.

This is what I had to start from:

class NumericalEntityProcessor {

    List<Integer[]> pairsThatSumToX(List<Integer> input, Integer expectedSum) {

    }
}

These are 2 of the possible solutions - but I missed something...

class NumericalEntityProcessor {

    List<Integer[]> pairsThatSumToX(List<Integer> input, Integer expectedSum) {

    int n = list.size() + 2;
    int expectedSum = n * (n + 1) / 2;
    int expectedSquaredSum = n * (n + 1) * (2 * n + 1) / 6;
    int sum = 0;
    int squaredSum = 0;

    System.out.println("SIZE :::" + list.size());

    for (Object num : list) {
        sum = sum + (int)num;
        squaredSum = squaredSum + ((int)num * (int)num);
    }

    int xplusy = expectedSum - sum;
    int xsquareplusysquare = expectedSquaredSum - squaredSum;
    int twoxy = xplusy * xplusy - xsquareplusysquare;
    int xminusy = (int) Math.sqrt(xsquareplusysquare - twoxy);
    int x = (xplusy + xminusy) / 2;
    int y = (xplusy - xminusy) / 2;

    return new Integer[] { x, y };

   int sum = list.stream().map(Line::getLength).collect(Collectors.summingInt(i->i)); 
  }
}

Or, second attempt-

public class ArrayExample1 {

    public static void main(String[] args) {

        int[] number = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

        List<Integer> list = convertIntArrayToList(number);
        System.out.println("list : " + list);

    }

    private static List<Integer> convertIntArrayToList(int[] input) {

        List<Integer> list = new ArrayList<>();
        for (int i : input) {
            list.add(i);
        }
        return list;
        IntSummaryStatistics stats = list.stream()
                     .collect(Collectors.summarizingInt(Line::getLength));
        IntSummaryStatistics stats = list.stream().flatMap(a->Arrays.stream(a))
                     .collect(Collectors.summarizingInt(i->i));
        System.out.println(stats.getSum());     
        }
    }
}

Answer 1

1. Sort the list
2. Define two pointers, one starting at head and incrementing, the other starting at tail and decrementing
3. Move a pointer while the total of the referenced numbers is less than the target
4. After iteration, note if the current numbers total the target
5. Repeat step 3 with the other pointer
6. Exit iteration if the total exceeds the target

Due to the sort, this algorithm has O(n log n) time complexity. The iteration part is O(n), which is ignored for the purposes of determining the overall time complexity because it has a lower order.