美文网首页
leetcode - python - 两数之和

leetcode - python - 两数之和

作者: creamelody | 来源:发表于2018-09-05 16:48 被阅读0次
    给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。
    你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。

    示例:
    给定 nums = [2, 7, 11, 15], target = 9
    因为 nums[0] + nums[1] = 2 + 7 = 9
    所以返回 [0, 1]

    方法一:使用全部遍历的方法(时间复杂度高)
    def twoSum(sums, target):
        n = len(sums)
        for i in range(n):
            for j in range(i+1, n):
                if sums[j] == target - sums[i]:
                    return i,j
                    break
                else:
                    continue
    
    方法二:直接从list中查找是否存在差值
    def twoSum(nums, target):
            n = len(sums)
            for i in range(n):
                    a = target - nums[i]
                    if a in nums:
                            j = nums.index(a)
                            if i == j:
                                    continue
                            else:
                                    return i,j
                                    break 
                    else:
                            break
    

    存在的问题:如果list中有两个相同的数,例如nums = [3,3], target = 6,最后返回值为(1, 0),因为index(a)得到的永远是第一个遍历到的数,而增加条件使i==j的时候继续,也就是此时第一次不返回值,而在之后遍历时自然而然的将遍历得到的a与原来的nums[i]调换位置。

    方法三:使用字典(还没有看懂,先🐎)
    def twoSum(self,nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: List[int]
            """
            #用len()方法取得nums列表长度
            n = len(nums)
            #创建一个空字典
            d = {}
            for x in range(n):
                a = target - nums[x]
                #字典d中存在nums[x]时
                if nums[x] in d:
                    return d[nums[x]],x
                #否则往字典增加键/值对
                else:
                    d[a] = x
            #边往字典增加键/值对,边与nums[x]进行对比
    

    转:这个解法是我看了排名前几个的答案后才知道的, 先创建一个空字典,然后依次把target-nums[x]的值存入字典,存入一个就跟nums[x+1]去比较, 字典中的key为target-nums[x],value为x,也就是nums[x]在nums列表中的索引位置。当字典d中有nums[x+1]时,也就是target - nums[y] = nums[x+1] , y肯定是小于x+1的(因为y是x+1之前循环过的数字),所以是 return y,x+1

    相关文章

      网友评论

          本文标题:leetcode - python - 两数之和

          本文链接:https://www.haomeiwen.com/subject/vioawftx.html