LeetCode167-Two Sum II – Input array is sorted

题目

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 and you may not use the same element twice.

Example:

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

分析

解法一:暴力匹配

最初想到的是直接从头遍历数组,取到该数的值,然后target – numbers[i]得到待匹配的另外一个值other,然后再用二重循环,从i + 1开始遍历查找是否有该值的存在,若有则匹配成功。该算法超时。

解法二:暴力二分匹配

解法一暴力的穷举查找显然是可以用二分查找改进的,因此我们又可设置高低两指针:low = i + 1 和 high = numbers.length – 1,然后用二分查找算法在[low, high]区间查找另外一值other。该算法超时。

解法三:双指针匹配

然而更优雅一点的是这个\(O(n)\)的方法:设置双指针low和high,然后根据下面情况作出调整:

  • numbers[low] + numbers[high] < target:需要增大,low++,high不动
  • numbers[low] + numbers[high] > target:需要减小,high–,low不动
  • numbers[low] + numbers[high] = target:匹配成功,返回

该算法运行时间为1ms,击败44%的人。

解法四:双指针 + 二分匹配

仔细观察上面的解法,其实还有可改进之处。我们不妨看看numbers[low] + numbers[high] < target时的这种情况:既然已然发现目前的和比target小,也意识到应该向后移动low指针把和调大,那为什么我们要一位一位地调呢?能不能快速地定位到最接近target的那个值呢?答案是可以的。因为我们其实还个重要信息没有利用!那就是达到恰好匹配时应该调大的差值,即gap = target – numbers[high],有了它我们便可以在数组的子区间[low + 1, high]内查找这个差值,找到这个差值的位置,便可以确定low应该调大的位置(下标),调大了,再在下一轮中比较numbers[low] + numbers[high] 与target的大小,此时要么相等,要么就该轮到high调小了。该算法运行时间为0ms,击败99%的人。

代码

解法一

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int other; //匹配的另一个数
        for (int i = 0; i < numbers.length - 1; i++) {
            other = target - numbers[i];
            for (int j = i + 1; j < numbers.length; j++) {
                if(numbers[j] == other)
                    return new int[] {i + 1, j + 1};
                else if (numbers[j] > other)
                    break;
            }
        }
        
        return null;
    }
}

解法二

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int other; //匹配的另一个数
        int low,high,mid;
        for (int i = 0; i < numbers.length - 1; i++) {
            other = target - numbers[i];
            
            //二分查找other
            low = i + 1;
            high = numbers.length - 1;
            while(low <= high) {
                mid = (low + high) / 2;
                if (other > numbers[mid]) low = mid + 1;
                else if (other < numbers[mid]) high = mid - 1;
                else return new int[] {i + 1, mid + 1};
            }
        }
        
        return null;
    }
}

解法三

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
   
        int low = 0;
        int high = numbers.length - 1;
        int sum;
        while(low <= high) {
            sum = numbers[low] + numbers[high];
            if (sum < target) low++;
            else if (sum > target) high--;
            else return new int[] {low + 1, high + 1};
        }
        
        return null;
    }
}

解法四

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
   
        int low = 0;
        int high = numbers.length - 1;
        int sum;
        while(low <= high) {
            sum = numbers[low] + numbers[high];
            if (sum < target) low = binarySearch(numbers, low + 1, high, target - numbers[high]);
            else if (sum > target) high = binarySearch(numbers, low, high - 1, target - numbers[low]);
            else return new int[] {low + 1, high + 1};
        }
        
        return null;
    }
    
    int binarySearch(int[] numbers, int low, int high, int target) {
        int mid;
        while(low < high) {
            mid = (low + high) / 2;
            if (target > numbers[mid]) low = mid + 1;
            else if (target < numbers[mid]) high = mid - 1;
            else return mid;
        }
        
        return low;
    }
}

Leave a Comment.