写在coding前
题目(Easy)
给定一个整数数列，找出其中和为特定值的那两个数，并返回这符合条件的数的下标。
你可以假设每个输入都只会有一种答案，同样的元素不能被重用。
示例：
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
我的解决方案：
class Solution:
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
# 返回的下标列表
rList = []
# 记录已经找到的符合条件的数值,用来保证：每个输入都只会有一种答案，同样的元素不能被重用
valueList = []
# 遍历列表
for i in range(len(nums)):
for j in range(i+1, len(nums)):
if nums[i] + nums[j] == target:
# 如果满足条件的数值之前没有遇到过，则将其下标加入列表
if nums[i] not in valueList:
rList.append(i)
if nums[j] not in valueList:
rList.append(j)
valueList.append(nums[i])
valueList.append(nums[j])
return rList
def main():
# 自定义测试用例
rList = Solution().twoSum([2, 7, 11, 15, 3, 2, 18, 6], 9)
print(rList)
if __name__ == '__main__':
main()
以上是我首先能想到的穷举算法,很明显这是最基础的做法,也叫暴力穷举.算法复杂度为:
时间复杂度为:O(N2)
空间复杂度为:O(1)
算法进化
我们知道对元素的搜索最快则是O(1)，即直接索引到，联想只能是Hash表或者是关键字索引。关键字索引（从最小到最大）会占用额外的内存空间。
由于笔者在刷题的过程中顺便想练习一下Python基本语法,所以这里直接采用 Python的dict.
另外我们要求的是元素的索引，即Hash表的关键字，所以我们把数组元素作为dict的key，而把数组元素的索引作为dict的value
def twoSum(self, nums, target):
# 相当于哈希表
dic = {}
rList = []
valueList = []
# 我们要求的是元素的索引，即Hash表的关键字，所以我们把数组元素作为dict的key，而把数组元素的索引作为dict的value
for i in range(len(nums)):
dic[nums[i]] = i
for i in range(len(nums)):
# 防止将同一对符合条件的值重复加入
if i not in rList:
# 将符合条件的两个元素成为互补元素
# 差值是字典的key且对应互补元素的下标不是当前元素的下标
if (target - nums[i]) in dic.keys() and dic[target - nums[i]] != i:
# 当前元素没有参与过之前的互补配对
if nums[i] not in valueList:
rList.append(i)
rList.append(dic[target - nums[i]])
valueList.append(nums[i])
return rList
采用哈希表来计算实际上是一个空间换时间的策略,该算法的算法复杂度为:
时间复杂度为:O(N)
空间复杂度为:O(N)
他山之石
网上查相关资料,有 先排序再用二分法 求符合条件的值的方法.但是,这里涉及到排序后原来的索引对应关系就都变了,这个时候找到符合条件的值后还需要找出对应原数组的索引,因为题目要求返回的是索引!
def twoSum(self, nums, target):
dic = {}
rList = []
valueList = []
# 使用numpy对数组进行排序
x = np.array(nums)
pynums = np.sort(x)
pyindexs = np.argsort(x)
ahead = len(nums) - 1
behind = 0
# 从有序数组两边向中央逼近
while ahead > behind:
if pynums[ahead] + pynums[behind] == target:
rList.append(pyindexs[behind])
rList.append(pyindexs[ahead])
ahead = ahead - 1
behind = behind + 1
elif pynums[ahead] + pynums[behind] < target:
behind = behind + 1
elif pynums[ahead] + pynums[behind] > target:
ahead = ahead - 1
return rList
这里的时间复杂度主要花在了对数组排序上,这里直接使用了python里的numpy.
由于python里的numpy可以对数组排序并返回排序后原数组下标,这样我们找到符合条件的值就比较容易找到原数组对应的下标了.该方法算法复杂度为:
时间复杂度为:O(NlogN)
空间复杂度为:O(N)
.
.
.
下一篇:2. 两数相加(AddTwoNumbers)
------------------------------20180308夜
刷Leetcode，
在我看来，
其实是为了维持一种编程状态！
