167.Two Sum II - Input array is sorted

Posted on | In

Solution 1: 1ms

Some binary thinking in the middle but not enough. We could make the time complexity closer to O(logn). 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int[] twoSum(int[] nums, int target) {
    if (nums.length < 2) return null;
    int lo = 0;
    int hi = nums.length - 1;
    while (true) {
        int sum = nums[lo] + nums[hi];
        if (sum == target) break;
        int mid = lo + (hi - lo) / 2;
        if (nums[lo] + nums[mid] > target) {
            hi = mid;
            continue;
        }
        if (nums[mid] + nums[hi] < target ) {
            lo = mid;
            continue;
        } 
        if (sum > target)hi--;
        else lo++;
    }
    return new int[] {++lo, ++hi};
}