twoSum_O(n log n)

class Solution {
    public int[] twoSum(int[] nums, int target) {
        
        int n = nums.length;
        int [][] arr = new int[n][2];
        
        for (int i=0; i < n; i++) {
            arr[i][0] = nums[i];
            arr[i][1] = i;
        }
        
        Arrays.sort(arr, new java.util.Comparator<int[]>() {
            public int compare(int [] a, int [] b) {
                return Double.compare(a[0], b[0]);
            }
        });
        
        int i = 0, j = n-1;
        
        int[] result = new int[2];
        while ( i < j ) {
            if (arr[i][0] + arr[j][0] == target) {
                result[0] = Math.min(arr[i][1], arr[j][1]);
                result[1] = Math.max(arr[i][1], arr[j][1]);
                break;
            } else if ( arr[i][0] + arr[j][0] > target) {
                j--;
            } else {
                i++;
            }
        }
        
        return result;
    }
}