package advanced.scan.twopointers.lc167_twosum2;

/**
 * Given an array of integers that is already sorted in ascending order, find two numbers such that
 * they add up to a specific target number. The function twoSum should return indices of the two numbers
 * such that they add up to the target, where index1 must be less than index2.
 * Please note that your returned answers (both index1 and index2) are not zero-based.
 * You may assume that each input would have exactly one solution.
 * Input: numbers={2, 7, 11, 15}, target=9
 * Output: index1=1, index2=2
 */
public class Solution {

    // My 3AC
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0, j = nums.length - 1; i < j; ) {
            if (nums[i] + nums[j] < target) i++;
            else if (nums[i] + nums[j] > target) j--;
            else return new int[] { i + 1, j + 1 };
        }
        return new int[] { -1, -1 };
    }

    // My 2AD: O(N) scan algorithm
    public int[] twoSum2(int[] nums, int target) {
        for (int i = 0, j = nums.length - 1; i < j; ) {
            if (nums[i] + nums[j] < target) {
                i++;
            } else if (nums[i] + nums[j] > target) {
                j--;
            } else { /* nums[i] + nums[j] == target */
                return new int[] { i + 1, j + 1 };
            }
        }
        return new int[] { -1, -1 };
    }

}

@@ -43,16 +43,42 @@
 osum2;%0A%0A
+import java.util.Arrays;%0A%0A
 /**%0A * G
@@ -613,16 +613,396 @@
 tion %7B%0A%0A
+    // O(NlogN) time binary search solution.%0A    public int%5B%5D twoSum(int%5B%5D nums, int target) %7B%0A        int n = nums.length;%0A        for (int i = 0; i %3C n; i++) %7B%0A            int j = Arrays.binarySearch(nums, i + 1, n, target - nums%5Bi%5D);%0A            if (j %3E= 0) %7B%0A                return new int%5B%5D%7B i + 1, j + 1 %7D;%0A            %7D%0A        %7D%0A        return new int%5B%5D%7B -1, -1 %7D;%0A    %7D%0A%0A
     // M
@@ -1022,32 +1022,33 @@
 lic int%5B%5D twoSum
+3
 (int%5B%5D nums, int

two sum II