https://leetcode-cn.com/problems/two-sum
代码:
# -*- coding:utf-8 -*- class Solution(object): def twoSum(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[int] """ temp = [target - nums[i] for i in range(len(nums))] for i in range(len(nums)): flag = nums[i] for j in range(len(temp)): if temp[j] == flag and i != j: return [i, j] if __name__ == '__main__': nums = [2, 7, 11, 15] nums = [3, 2, 4] target = 6 print(Solution().twoSum(nums, target))
思路:这道题我做的时候倒是没用什么具体的算法,只是利用一个辅助数组,其值为target – nums[i],然后对比两个列表中是否有相同的元素,需要注意的就是第二层循环中的判断需要加 i != j 以防止自比较问题,第一次提交就是因为没有想到这个结果错了。
思考:但是我这里的对比列表用的是一个双层循环,这使得整个算法的时间复杂度上升到了n^2,查看评论后,对比可以换成字典,这样在字典中查找总的时间复杂度就会降到nlgn。
def twoSum(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[int] """ hashmap = {} for index, num in enumerate(nums): another_num = target - num if another_num in hashmap: return [hashmap[another_num], index] hashmap[num] = index return None
0 条评论