首页 > 代码库 > leetcode sum相关算法题
leetcode sum相关算法题
1. Two Sum(https://oj.leetcode.com/problems/two-sum/)
解题思路：
解法一： 暴力，O(n2)时间复杂度，TLE
解法二：利用hash, 记录下数组中每个值对应的下标，再遍历一遍数组，通过查看target-num[i]的值是否在map中来确定另一个数值。时间复杂度O(n)
解法三：对num数组排序，O(nlog(n)), 然后左右夹逼O(n). 但这道题要求记录下标，故这个方法行不通。
python代码如下：
1 def twoSum(self, num, target): 2 d = {} 3 lenNum = len(num) 4 ans = [] 5 for i in xrange(lenNum): 6 d[num[i]] = [i+1] if num[i] not in d else d[num[i]] + [i+1] 7 for i in num: 8 res = target - i 9 if res in d:10 if res == i:11 if len(d[i]) == 2: return (d[i][0], d[i][1])12 else:13 return (d[i][0], d[res][0]) if d[i][0] < d[res][0] else (d[res][0], d[i][0])
leetcode sum相关算法题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。