Linear Algorithm for 2SUM on a sorted array.

TwoSum.java

    // If Array was already sorted
    // Complexity - O(n)
    private int[] findPair_4(int[] A) {
        int left = 0, right = A.length - 1;
        while (left < right) {
            int s = A[left] + A[right];
            if (s == 0)
                return new int[]{A[left], A[right]};
            else if (s > 0)
                right--;
            else
                left++;
        }
        return null;
    }