两个数的和

在给定的一些数字中找出两个数，使得他们的和为N，前提是数据中保证有答案，并且只有一个答案。例如给定5个数字：3，4，5，7，10，从中选择两个数使他们的和为11，可以选择4和7，如何解决这个问题？

第一种求和方法

先将数组从小到大排序，排序时需要把数据复制到一个新的数组中，然后对新的数组进行排序。

数组排序后，可以开始查找了。建立两个指针left和right，分别指向新数组的第一个元素和最后一个元素。如果俩个指针的两个数据相加的和等于目标值，那么查找结束，返回这两个数的下标，如果他们的和小于目标值，则说明left指向的数据太小了，需要让left指针向右移动一位；如果他们的和大于目标值，则说明right指向的数据太大了，需要让right指针向左移动一位。重复这个过程，直到找到答案。

源代码：

#方法1
def twoSum(nums, target):
    res = []  #存放结果编号数据
    newnums = nums[:]  #深拷贝，把源数据复制到newnums里
    newnums.sort()   #对新数组排序
    left = 0
    right = len(newnums) - 1#定义left和right指针分别指向新数组的开头和结尾
    while left < right:
        if newnums[left] + newnums[right] == target:
            for i in range(0, len(nums)):   #在原始数组中寻找第一个元素的原始下标
                if nums[i] == newnums[left]:
                    res.append(i)   #将下标加入结果集
                    break
            for i in range(len(nums) - 1, -1, -1):    #在原始数组中寻找第二个元素的原始下标
                if nums[i] == newnums[right]:
                    res.append(i)  #将下标加入结果集
                    break

            res.sort()
            break
        elif newnums[left] + newnums[right] < target:
            left += 1             #让left指针向右移动一位
        elif newnums[left] + newnums[right] > target:
            right -= 1             #让right指针向左移动一位
    return (res[0] + 1, res[1] + 1)  #返回结果集


if __name__ == '__main__':
    print(twoSum([3, 4, 5, 7, 10], 11))

运行：

第二种方法

使用哈希算法。先建立一个字典。
每当给定一个数m，问题就变成了数据集合中是否有一个数target-m，可以通过使用字典记录目前已经出现过那些数字，这样每次出现一个新的数字时，就去字典中查找有没有对应的数字，如果有则说明找到了，没有的话就把该数放到字典中去，以备以后查询使用。

使用字典记录数据，再去字典中查找数据的方式就是哈希方法，使用统一的哈希函数把数据对存储到字典中，在使用统一的哈希函数从字典中把数据取出来，理论上是可以达到常数级别的查询速度的。

源代码：

#方法2
def twoSum(nums,target):
    dict = {}
    for i in range(len(nums)):
        m = nums[i]      #定义m为当前待查询的数字
        if target - m in dict:   #判定target-m是否已经在字典中
            return(dict[target - m] + 1,i + 1)  #如果已经存在，则返回这两个数的下标
        dict[m] = i  #如果不存在则记录键值对
        
if __name__ == '__main__':
    print(twoSum([3,4,5,7,10], 11))

运行：