package org.pilgrim.leetcode.y2022;

import java.util.Arrays;

public class SumTwoInSorterArray {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		int[] indexes = twoSum(new int[] {1,2,3,4,4,9,56,90}, 8);
		System.out.println(Arrays.toString(indexes));
	}
	
	public static int[] twoSum(int[] arr, int k) {
        // Validate input values
        if(arr == null || arr.length <= 1 || arr.length > 3 * 10000 || k< -1000 || k > 1000){
            return null;
        }
        
        // Traverse array from both sides
        int[] res = new int[] {-1, -1};
        int i = 0;
        int j = arr.length - 1;
        while(i < j){
            int s = arr[i] + arr[j];
            if(k == s){
                res[0] = i+1;
                res[1] = j+1;
                break;
            }
            else if(k > s){
                i++;
                while(i < j && arr[i] == arr[i+1] && arr[i]*2 != k){
                    i++;
                }
            }
            else if(k < s){
                j--;
                while(i < j && arr[j] == arr[j - 1] && arr[j]*2 != k){
                    j--;
                }
            }
        }
        
        return res;
    }
	
	public static int[] twoSum2(int[] numbers, int target) {
        int left = 0, right = numbers.length - 1;
        while (left < right) {
            int sum = numbers[left] + numbers[right];
            int mid = left + (right - left) / 2;
            if (sum > target)
                if (numbers[left] + numbers[mid] > target)
                    right = mid - 1;
                else
                    right--;
            else if (sum < target)
                if (numbers[mid] + numbers[right] < target)
                    left = mid + 1;
                else
                    left++;
            else
                return new int[] {left +1, right + 1};
        }
        return null;
    }

}

@@ -30,16 +30,1342 @@
 y2022;%0A%0A
+/**%0A * %0A * 167. Two Sum II - Input Array Is Sorted%0AMedium%0A%0A5664%0A%0A953%0A%0AAdd to List%0A%0AShare%0AGiven a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers%5Bindex1%5D and numbers%5Bindex2%5D where 1 %3C= index1 %3C index2 %3C= numbers.length.%0A%0AReturn the indices of the two numbers, index1 and index2, added by one as an integer array %5Bindex1, index2%5D of length 2.%0A%0AThe tests are generated such that there is exactly one solution. You may not use the same element twice.%0A%0AYour solution must use only constant extra space.%0A%0A %0A%0AExample 1:%0A%0AInput: numbers = %5B2,7,11,15%5D, target = 9%0AOutput: %5B1,2%5D%0AExplanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return %5B1, 2%5D.%0AExample 2:%0A%0AInput: numbers = %5B2,3,4%5D, target = 6%0AOutput: %5B1,3%5D%0AExplanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return %5B1, 3%5D.%0AExample 3:%0A%0AInput: numbers = %5B-1,0%5D, target = -1%0AOutput: %5B1,2%5D%0AExplanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return %5B1, 2%5D.%0A %0A%0AConstraints:%0A%0A2 %3C= numbers.length %3C= 3 * 104%0A-1000 %3C= numbers%5Bi%5D %3C= 1000%0Anumbers is sorted in non-decreasing order.%0A-1000 %3C= target %3C= 1000%0AThe tests are generated such that there is exactly one solution.%0A * %0A * %0A */%0A%0A
 import j

add description