本文共 3323 字，大约阅读时间需要 11 分钟。

题目介绍

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.

该函数应该可以返回两个数字的索引，他们的和为某个特殊的数字，并且索引1必须比索引2小

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 1:

Input: numbers = [2,7,11,15], target = 9Output: [1,2]Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1,  index2 = 2.

Example 2:

Input: numbers = [2,3,4], target = 6Output: [1,3]

Example 3:

Input: numbers = [-1,0], target = -1Output: [1,2]

Constraints:

• 2 <= nums.length <= 3 * 104
• -1000 <= nums[i] <= 1000
• nums is sorted in increasing order.
• -1000 <= target <= 1000

参考Two Sum解决

一、Brute Force 暴力实现

思路分析

• 两数相加，列出所有的两个数组的组合。采用二重循环遍历

C语言实现

/** * Note: The returned array must be malloced, assume caller calls free(). */int* twoSum(int* numbers, int numbersSize, int target, int* returnSize){
       for(int i = 0;i < numbersSize - 1;i ++)    {
           for(int j = i + 1;j < numbersSize;j ++)        {
               if(numbers[i] + numbers[j] == target)            {
                   int *result = NULL;                result = (int *)malloc(sizeof(int) * 2);                result[0] = i + 1;                result[1] = j + 1;                *returnSize = 2;                return result;            }        }    }    *returnSize = 0;    return NULL;}

分析与总结

• 使用指针一定要先明确指向，在使用。否则会犯如下的错误，
  • resultSize并没有指向实际的内存空间，所以修改*resultSize的指向并不会带了任何的改变

二、Hash表实现

思路分析

• 将所有的数组元素以 “ 数值 ：索引 ”的键值对的方式，构成对应的字典。
• 接着hashtable查找快速的方式去减少查找特定元素的时间

python实现

class Solution(object):    def twoSum(self, numbers, target):        """        :type numbers: List[int]        :type target: int        :rtype: List[int]        """        adict = dict()        for index,value in enumerate(numbers):            temp = target - value            if temp in adict:                return list(sorted([index + 1,adict.get(temp) + 1]))            else:                adict[value] = index        return []

分析总结

• sort（）和sorted（）的区别，sort（）是改变原来的数组，sorted是不改变原来的数组，返回的是排序过后的新数组

三、左右边界法

思路分析

• 不同于乱序的数列，题目中所给的数列是按照升序排列过的，意味着：越往左，数字越大；越往右，数字越小
• target=a + b，且a.index <= b.index ,说明a <= b。
• 所以可以设想：
  • a从最小的数字按照递增的方式开始向右遍历
  • b从最大的数字按照递减的方式开始向左遍历
  • a+b > target，说明数字要变小，b往左移动，减少a + b的值
  • a+b <target ，说明数字要变大，a往有移动，增加a + b的值
  • a + b = target，说明相等，直接返回对应的索引即可

C语言实现

/** * Note: The returned array must be malloced, assume caller calls free(). */int* twoSum(int* numbers, int numbersSize, int target, int* returnSize){
       int left = 0, right = numbersSize - 1;    while(left < right)    {
           if(numbers[left] + numbers[right] == target)        {
               *returnSize = 2;            int *result = NULL;            result = (int *)malloc(sizeof(int)* 2);            result[0] = left + 1;            result[1] = right + 1;            return result;        }        else if(numbers[left] + numbers[right] > target)        {
               right --;        }        else        {
               left ++;        }    }    *returnSize = 0;    return NULL;}

转载地址：http://gggpb.baihongyu.com/