算法-两数之和
2018-07-22 本文已影响0人
辉辉12306
这是一道LeetCode上的问题，详见两数之和，难度标注是简单，但是我思考到了一些比较复杂的情况，之后我会修改题目进行讨论的。
废话不多，先看题：
给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。
简单的说，就是寻找到两个数之和等于目标值的两个数序号，且只用寻找一个解。
暴力解法
寻找每一个搭配即可。
复杂度分析：
| 时间复杂度 | 空间复杂度 |
|---|---|
| n^2 | 1 |
python代码：
def twoSum(self, nums, target):
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
哈希映射
上面的暴力求解法速度慢，主要的原因是优于在确定第一个数之后，需要使用挨个遍历的办法来寻找另一个数是否存在，而在挨个遍历的过程中，又带来了时间复杂度O(n)，所以如果很快的寻找出另一个数的话，那么时间复杂度就可以降低了，理所应当的想到，能做到快速查找的办法就是散列表/哈希。
具体方法：
使用hash建立 item->index 的映射关系，通过 target-item 反向查找hash是否存在这个index，因为hash的查找时间是O(1)的时间复杂度，所以复杂度如下。
复杂度分析：
| 步骤 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| hash映射 | n | n |
| 反向寻找 | n | 1 |
| 总计 | n | n |
python代码：
def twoSum(self, nums, target):
# 产生散列表
hash_ = dict(zip(nums, range(len(nums))))
# 反向寻找
for i in range(len(nums)):
other=target-nums[i]
if hash_.get(other):
return [i,hash_[other]]
问题
从时间复杂度的方向考虑，哈希已经可以做到很好了，但是实际情况中问题不是总是如题目中的简单要求，因此可能会有下图可能：
[图片上传失败...(image-848eab-1532229850821)]
- 针对两数之和等于目标值 and 一个组合的情况上面的已经给出解决方案
- 针对两数之和等于目标值 and 所有组合的情况可以在散列表产生的时候，不是采用键值覆盖的方式，而是使用list表单存储所有这个元素的位置，产生散列表的代码如下（没有经过测试）
# 原代码：hash_ = dict(zip(nums, range(len(nums))))
hash_={}
for i in range(len(nums)):
if hash_.get(nums[i]):
# 如果存在hash，那么就存储进去
hash_[nums[i]].append(i)
else:
hash_[nums[i]]=[i]
- 针对两数之和接近目标值 and 一个组合/所有组合的情况，就不能再使用散列表的方法了，因为散列表能够工作的原因就是在知道第一个数的时候，另一个数会唯一确定，因此可以反向查找，但是现在不成立，我这里提供了另一个办法（也是针对题目的要求，但是也可以修改后针对这种要求），时间复杂度略有损失。
有序线性查找
先进行排序，然后根据有序性，线性查找。
具体步骤：
- 升序排序，我使用的是merge排序，但是因为最后希望找到序号的值，所以不能直接排序，而是排列序号，在numpy中可以使用argsort排序
- start指针指向第一个元素，尝试寻找start指针和end指针之和刚刚大于等于target的end指针位置，也就是end指针的位置是大于等于target的，但是end指针之前的位置是小于target的
- 开始寻找，如果之和小于target，那么start增加；如果之和大于target，那么end减少，知道start和end指针相遇。针对为什么小于target时start增加，而非end增加，因为end在这个步骤中的操作是减少，之前（也就是比end大）的值已经搜索过了，反之亦然。
复杂度分析：
| 步骤 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| marge排序 | nlogn | n |
| 搜索 | n | 1 |
| 总计 | nlogn | n |
python代码，不包含第三方库（也可以使用numpy.argsort）
from math import floor
from copy import copy as py_copy
def argsort(nums):
arg = list(range(len(nums)))
def get(i, list_index=None):
if list_index is None:
list_index = arg
return nums[list_index[i]]
def set(i, index):
arg[i] = index
def copy(start, end):
return py_copy(arg[start:end + 1])
def sort_merge_core(start, end):
"""
merge排序
分治策略：
分解：数组二分，每个小数组排序
解决：对于最小的数组，长度1，不需要排序
合并：两个有序的数组，合并成为一个有序的数组
start：排序的头指针，包括本身
mid：分解的中间指针，i~j是分解的第一个数组，j+1~k是分解的第二个数组
end：排序的尾指针，包括本身
"""
if start < end:
mid = floor((start + end) / 2)
sort_merge_core(start, mid)
sort_merge_core(mid + 1, end)
merge(start, mid, end)
def merge(start, mid, end):
"""
合并
i1：第一个数组的指针，还没有发到的位置
i2：第二个
index：发牌的指针，指向A，说明将要需要放置的位置
"""
i1, i2 = 0, 0
A1 = copy(start, mid)
A2 = copy(mid + 1, end)
for index in range(start, end + 1):
if i2 == len(A2) or i1 != len(A1) and get(i1, A1) < get(i2, A2):
set(index, A1[i1])
i1 += 1
else:
set(index, A2[i2])
i2 += 1
sort_merge_core(0, len(nums) - 1)
return arg
def twoSum(self, nums, target):
start = 0
end = len(nums) - 1
# 从小到大排序，并保存原来的顺序
nums_index = argsort(nums)
def getSum():
return nums[nums_index[end]] + nums[nums_index[start]]
# start和end之和刚刚大于等于target
while getSum() > target:
end -= 1
if getSum() < target and end + 1 < len(nums):
end += 1
# 开始寻找，如果小于start增加，如果大于end减少
while True:
if start >= end:
return None
if getSum() < target:
start += 1
elif getSum() > target:
end -= 1
else:
return sorted([nums_index[start], nums_index[end]])
结语
这个题目本身并不复杂，但是我认为这种深入思考的方式，还是要坚持的使用，举一反三，事半功倍。欢迎来我的github逛逛，还有我的博客。如果有什么问题或者探讨，留言和email(jingege315@gmail.com)都是欢迎的。
