【leetcode刷题】T3-Two Sum II

今天本来打算更新3sum closest这道题，但是发现需要用到Two Sum II的思想。

今天分享leetcode第3篇文章，也是leetcode第167题—Two Sum II - Input array is sorted，地址是：https://leetcode.com/problems/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.

Note:

• 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: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.

【中文题目】

给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。

函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。

说明:

• 返回的下标值（index1 和 index2）不是从零开始的。
• 你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

示例:

输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

【思路】

本题和Two Sum是同一题，只是添加了『数组有序』这个条件，因此也有自己独特的解法。

我们回忆一个场景：食堂阿姨打菜时，如果她认为菜多了，会手抖抖出一部分菜；而当她认为菜少了，打了一勺后，会再打一点（哪有这样的阿姨，黑人问号脸）。

（本科一个期末考试阶段，一个姑娘去食堂打菜，跟打菜大叔说，“叔叔少打一点，吃不完”，大叔却给她狠狠舀了一勺菜，说“那不得行！要多吃点，才有力气复习”）

那么是不是我们也可以这样？先取出两个数，当两数之和过大时，就“少打点“，取其左边的数试试；当两数之和过小时，就“多打点”，取其右边的数试试。

那么我们选哪两个数呢？能不能当两数之和不等于target时，确定地选取一个数的左边或者右边的数进行尝试呢？

当然可以，我们选择第一个数和最后一个数！(假设a指向较小的数，即第一个数；b指向较大的数，即最后一个数)

当两数之和过大时，b指向其左边的数（即倒数第二个数）尝试；当两数之和过小时，a指向其右边的数（即第二个数）尝试，以此类推。

为什么可以这样呢？我们给出一个例子，数组是[1, 3, 3, 4, 8]，target是6

我们首先选择1、8，1+8=9> 6，于是b指向其左边的数4

这里选择1、4，1+4=5<6，于是a指向其右边的数3

这里选择3、4，3+4=7>6，于是b指向其左边的数3

这里选择3、3，3+3=6=6，于是返回两个下标

可以看出，时间复杂度为O(n)

值得注意的是，本题所指的下标从1开始

【代码】

python版本

class Solution(object):
   def twoSum(self, numbers, target):
       """
       :type numbers: List[int]
       :type target: int
       :rtype: List[int]
       """
       i, j = 0, len(numbers) - 1
       # 必定有一个满足条件
       # 不用考虑numbers[0] > target的情况等
       while i < j:
           if numbers[i] + numbers[j] == target:
               return [i+1, j+1]
           if numbers[i] + numbers[j] > target:
               j -= 1
           else:
               i += 1

C++版本

class Solution {
public:
   vector<int> twoSum(vector<int>& numbers, int target) {
       int i = 0, j = numbers.size() - 1;
       vector<int> res;
       while(i < j){
           if(numbers[i] + numbers[j] == target){
               res.push_back(i + 1);
               res.push_back(j + 1);
               break;
           }
           if(numbers[i] + numbers[j] > target){
               j--;
           }else{
               i++;
           }
       }
       return res;
   }
};

相关文章：

Two Sum

3Sum

昨天的3Sum在对数组排序后也可以此方法，有空了试试哟~