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.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

出处:https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/

原文大意

给定一个按升序排序的int类型数组和一个目标数target,在数组中查找两个数,使得这两个数之和等于target.
函数twoSum需要返回这两个数在数组中的下标index1,index2, 同时index1小于index2,注意:返回的下标不是以0为起始值.
假设每一组恰好只有一组解,并且数组中的元素不能被使用两次.

解题思路

题中以说明数组已排序,则很容易想到二分查找.

解法一:Binary Search

std::vector<int> twoSum(std::vector<int>& nums, int target) {
  int count = nums.size();
  //遍历一遍数组
  for (int i = 0; i < count-1; ++i)
  {
    int diff = target - nums[i];
    int istart = i+1, iend = count-1;
    //使用二分法,在数组中查找diff
    while(istart <= iend){
      //计算imid,
      // 不建议使用:imid = (istart+iend)/2,可能会内存溢出
      int imid = istart + (iend-istart)/2;
      if (nums[imid] == diff)
      {
        return {i+1, imid+1};
      }
      if (nums[imid] > diff)
      {
        iend = imid-1;
      }
      else{
        istart = imid+1;
      }
    }
  }
}

由于遍历了一遍数组,时间复杂度为O(N),同时内部运用二分查找,其时间复杂度为O(logN),则解法一的时间复杂度为

O(N)*O(logN) = O(NlogN)

此段代码提交到leetcode,其runtime为9ms.

解法二:Two Pointer

举一个例子:
int nums[] = {1,3,4,5,6,17, 18, 20, 30}
int target = 11
现在需要求两个下标lower, high使得nums[lower]+nums[high]=target,使用两个指针分别指向下标的最小值与最大值,则lower,high的初始值分别为0,nums-size()-1,如下图所示:
两个指针:lower = 0, high = nums.size()-1

若nums[lower]+nums[high]<target,则需要将lower向右移；

若nums[lower]+nums[high] > target,则需要将high向左移；

若nums[lower]+nums[high]=target,则lower与high即为所求之值；

std::vector<int> twoSum(std::vector<int>& numbers, int target){
  int lower = 0, high = numbers.size()-1;
  while(lower < high){
    //求target与numbers[lower]之差,
    //nums[lower]+nums[high] 可能会溢出
    int diff = target - numbers[lower];
    if (numbers[high] == diff){
      return {lower+1, high+1};
    }
    if(numbers[high] > diff){
      //右边的值比差值大
      high--;
    }
    else if(numbers[high] < diff){
      //右边的值比差值小
      lower++;
    }
  }
  return {};
}

使用两个指针从数组的两边遍历,最好的情况是lower与high在数组的两端,最坏的情况是lower与high在中间某一位置相遇(不一定是中位数),在这种情况下,会遍历整个数组,则时间复杂度为O(n).
此段代码提交到leetcode,其runtime为3ms.

后记

1. 二分法时间复杂度
   二分查找是在有序的数组中查找目标元素的方法,每次都拿中间的元素与目标元素比较,于是每次比较都可以减少一半的元素；
   比较0次后,元素有n个；
   比较1次后,元素有n/2个；
   比较2次后,元素剩余n/4个,即n/2/2;
   比较3次后,元素剩余n/8个,即n/2/2/2;
   …
   比较m次后,元素剩余n/2^m个;
   最坏的情况下,元素只剩下1个;

   n/2^m = 1;
   m = log2(n)
   

   则二分查找的时间复杂度为O(logN)