Very easy to understand java solution


  • 0
    A

    The idea is to try to find the number just greater than the target number in the array first, and get its index. Therefore, from that index, we cut off the right part of the array that is impossible to have the answers.

    public class Solution {
        public int[] twoSum(int[] numbers, int target) {
            int[] res = new int[2];
            int n = numbers.length;
            int i = 0;
            int left = 0;
            int right = n-1;
            //Find where to cut off the right part of the array
            while(left < right && right - left > 1){
                i = (left+right)>>1;
                if(numbers[i]>target) right = i;
                else if(numbers[i]<target) left = i;
                else break;
            }
            //Search results from both ends
            left = 0; right = i+1;
            while(left < right){
                if((target - numbers[left]) < numbers[right]){
                    right--;
                }else if((target - numbers[left]) > numbers[right]){
                    left++;
                }else{
                    res[0] = left+1;
                    res[1] = right+1;
                    break;
                }
            }
            return res;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.