leetcode 167: Two Sum II - Input array is sorted

leetcode 167: Two Sum II - Input array is sorted - 西施豆腐渣 - 博客频道 - CSDN.NET
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
https://discuss.leetcode.com/topic/6229/share-my-java-ac-solution

1. public int[] twoSum(int[] numbers, int target) {  
2.         if(numbers==null || numbers.length < 1) return null;  
3.         int i=0, j=numbers.length-1;  
4.           
5.         while(i<j) {  
6.             int x = numbers[i] + numbers[j];  
7.             if(x<target) {  
8.                 ++i;  
9.             } else if(x>target) {  
10.                 --j;  
11.             } else {  
12.                 return new int[]{i+1, j+1};  
13.             }  
14.         }  
15.         return null;  
16.     }  

严格来说，两个int的加和可能溢出int，因此将tmp和target提升为long long int再进行比较更鲁棒。

https://leetcode.com/discuss/82336/simple-8-line-java-solution-with-explanation-o-n
https://tech.liuchao.me/2016/11/leetcode-solution-167/
public int[] twoSum(int[] numbers, int target) { int l = 0, r = numbers.length - 1; while (numbers[l] + numbers[r] != target) { if (numbers[l] + numbers[r] > target) r--; else l++; } return new int[]{l + 1, r + 1}; }
X. O(nlogn) binary search
https://leetcode.com/discuss/22089/a-less-efficient-way-binary-search

Say, fix the first element A[0] and do binary search on the remaining n-1 elements. If cannot find any element which equals target-A[0], Try A[1]. That is, fix A[1] and do binary search on A[2]~A[n-1]. Continue this process until we have the last two elements A[n-2] and A[n-1].

Does this gives a time complexity lg(n-1) + lg(n-2) + ... + lg(1) ~ O(lg(n!)) ~ O(nlgn). So it is less efficient than the O(n) solution

You can add an early exit if target-numbers[i] > numbers[numbers.size()-1]. This can speed up the binary search.

vector<int> twoSum(vector<int> &numbers, int target) { if(numbers.empty()) return {}; for(int i=0; i<numbers.size()-1; i++) { int start=i+1, end=numbers.size()-1, gap=target-numbers[i]; while(start <= end) { int m = start+(end-start)/2; if(numbers[m] == gap) return {i+1,m+1}; else if(numbers[m] > gap) end=m-1; else start=m+1; } } }

public int[] twoSum(int[] numbers, int target) { for (int i = 0, n = numbers.length; i < n - 1; i++) { int j = Arrays.binarySearch(numbers, i + 1, n, target - numbers[i]); if (j > 0) return new int[]{i + 1, j + 1}; } return null; }

    public int[] twoSum(int[] numbers, int target) {
        boolean isBegin = true;
        int [] result = new int [2];
        int temp = 0, before = 0, end = numbers.length, index = 0;
        while(before<end){
            if(isBegin){
                temp = target - numbers[before];
                index = Arrays.binarySearch(numbers, before, end, temp);
                if(index > 0){
                    result[0] = before + 1;
                    result[1] = index + 1;
                    return result;
                }else{
                    end = -index - 1 - 1;
                    isBegin = false;
                }
            }else{
                temp = target - numbers[end];
                index = Arrays.binarySearch(numbers, before, end, temp);
                if(index > 0){
                    result[0] = index + 1;
                    result[1] = end + 1;
                    return result;
                }else{
                    before = -index - 1;
                    isBegin = true;
                }
            }
        }
    return result;
    }

https://leetcode.com/discuss/79034/another-binary-search-idea
Read full article from leetcode 167: Two Sum II - Input array is sorted - 西施豆腐渣 - 博客频道 - CSDN.NET