V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
Learn Python the Hard Way
Python Sites
PyPI - Python Package Index
http://diveintopython.org/toc/index.html
Pocoo
值得关注的项目
PyPy
Celery
Jinja2
Read the Docs
gevent
pyenv
virtualenv
Stackless Python
Beautiful Soup
结巴中文分词
Green Unicorn
Sentry
Shovel
Pyflakes
pytest
Python 编程
pep8 Checker
Styles
PEP 8
Google Python Style Guide
Code Style from The Hitchhiker's Guide
a476286557
V2EX  ›  Python

leetcode 两数之和 Python 求解答

  •  
  •   a476286557 · 2018-06-29 14:02:04 +08:00 · 4109 次点击
    这是一个创建于 2337 天前的主题,其中的信息可能已经有所发展或是发生改变。

    给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。

    你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。

    示例:

    给定 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]
        """
        list = []
        for i in nums:
            a = target - i
            if a != i:
                if a in nums:
                    index1 = nums.index(i)
                    list.append(index1)

    我想问问为这个为什么不对?谢谢

    24 条回复    2018-06-30 20:43:57 +08:00
    hand515
        1
    hand515  
       2018-06-29 14:44:06 +08:00
    target - i ??
    target - nums[i] 吧
    Kilerd
        2
    Kilerd  
       2018-06-29 14:47:13 +08:00
    list.append(index1)

    你只把第二个数的 index 放进去了。第一个数(i)的 index 没放进去。 而且找到之后 append 之后,应该直接 return
    a476286557
        3
    a476286557  
    OP
       2018-06-29 15:01:36 +08:00
    @hand515 我遍历的是列表 并没有遍历它的长度
    hand515
        4
    hand515  
       2018-06-29 15:03:59 +08:00
    我看错。。
    Ryans
        5
    Ryans  
       2018-06-29 15:13:13 +08:00
    for i in range(len(nums)):
    for j in range(i):
    if ( nums[j] == target - nums[i]):
    return [j,i]
    return [-1,-1]

    O(n^2) 暴力算法
    lyog
        6
    lyog  
       2018-06-29 15:43:36 +08:00 via iPhone
    hashMap 解决,key 为 target-nums[i],value 为 i
    casparchen
        7
    casparchen  
       2018-06-29 15:46:04 +08:00 via iPhone
    [1,3,4,3], target=6
    ballshapesdsd
        8
    ballshapesdsd  
       2018-06-29 15:46:55 +08:00
    这不是第一题么。。。
    sendohzhang
        9
    sendohzhang  
       2018-06-29 15:49:54 +08:00
    @Ryans

    for j in range(i) ??? 应该是 for j in range(len(nums))吧
    lyog
        10
    lyog  
       2018-06-29 15:52:20 +08:00 via iPhone
    @lyog 至于楼主问题,最后加个 list.append(nums.index ( a ))解决
    singed
        11
    singed  
       2018-06-29 16:16:38 +08:00
    for i, x in enumerate(nums):
    for j, y in enumerate(nums):
    if i != j and x + y == target:
    print(x, y)
    ingin
        12
    ingin  
       2018-06-29 16:37:36 +08:00

    有点 low
    maichael
        13
    maichael  
       2018-06-29 16:54:56 +08:00
    当两个数相等的情况下你的就炸了。

    比如[3, 3],target 6。
    a476286557
        14
    a476286557  
    OP
       2018-06-29 18:04:10 +08:00
    @maichael 哈哈 我也发现了 。
    mrlcy
        15
    mrlcy  
       2018-06-29 19:35:26 +08:00
    """
    @param A: array
    @param key: key word
    @param left: left side index of the array.
    @param right: right side index of the array.
    """
    def binary_search(A, key, left, right):
    """
    imp
    """
    def twoSums(self, nums, target):
    for i in range(0, len(nums)):
    key = target - nums[i]
    index = binary_search(nums, key, i, len(nums)-1)
    if (r is not -1):
    print((nums[i], nums[index]))

    nlog(n)的实现, 和你的思路类似。代码没有测试。
    fushall
        16
    fushall  
       2018-06-29 20:07:30 +08:00
    '''
    1. 两数之和

    给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。

    你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。

    示例:

    给定 nums = [2, 7, 11, 15], target = 9

    因为 nums[0] + nums[1] = 2 + 7 = 9
    所以返回 [0, 1]

    '''

    class Solution:
    # 执行用时:80 ms
    def twoSum(self, nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: List[int]
    """
    nums = [(value, index) for index, value in enumerate(nums)]
    nums.sort(key=lambda k:k[0])
    c = 0
    for x in nums:
    c += 1
    v = target - x[0]
    for y in nums[c:]:
    if not (y[0] - v):
    return [x[1], y[1]]
    necomancer
        17
    necomancer  
       2018-06-29 23:50:33 +08:00
    假定数组是 a,长度是 n, [ (i, j) for i,x in enumerate(a) for j,y in enumerate(a) if x + y == target and i<j ] 比较直观,复杂度是 O(n^2),大致看了下,至少你的 a!=i 就不允许列表中出现重复元素;并且最后也少放了另一个元素 a 的标号在结果里。

    第二个就是用 binary_search,当然,假定你的数组 a 是排好序的:

    [ idxes for idxes in ( (i, binary_search(target - x, i+1, n)) for i, x in enumerate(a) ) if idxes[1] != -1 ],比如用楼上那个失败返回 -1 的 binary_search,这样是 O(nlog(n))
    BaffinLee
        18
    BaffinLee  
       2018-06-30 00:07:46 +08:00
    js

    /**
    * @param {number[]} nums
    * @param {number} target
    * @return {number[]}
    */
    var twoSum = function(nums, target) {
    var hash = {};
    var len = nums.length;
    for (var i = 0; i < len; i++) {
    if (nums[i] in hash) return [hash[nums[i]], i];
    hash[target - nums[i]] = i
    }
    return [-1, -1];
    };

    https://baffinlee.github.io/leetcode-javascript/
    necomancer
        19
    necomancer  
       2018-06-30 00:13:53 +08:00
    EDIT:
    1. [ (i, j) for i,x in enumerate(a) for j,y in enumerate(a) if i<j and x + y == target ]
    2. [ idxes for idxes in ( (i, binary_search(a, target - x, i+1, n-1) ) for i, x in enumerate(a) ) if idxes[1] != -1 ]


    def binary_search(arr, hkey, start, end):
    ....while start <= end:
    ........mid = start + (end - start) // 2
    ........if arr[mid] < hkey:
    ............start = mid + 1
    ........elif arr[mid] > hkey:
    ............end = mid - 1
    ........else:
    ............return mid
    ....return -1
    IceCola1
        20
    IceCola1  
       2018-06-30 00:20:46 +08:00
    class Solution:
    def twoSum(self,nums, target):
    sd={}
    for index_i,i in enumerate(nums):
    if sd.get(target-i)!=target-i:
    sd[i]=i
    else:
    return [nums.index(target-i),index_i]
    IceCola1
        21
    IceCola1  
       2018-06-30 00:22:22 +08:00
    你们的都好长啊,我这个 44ms
    swulling
        22
    swulling  
       2018-06-30 06:59:54 +08:00 via iPhone
    标准答案哈希表,On
    ayyll
        23
    ayyll  
       2018-06-30 08:24:30 +08:00 via Android
    @swulling 楼上一堆暴力。。这题哈希应该不难想到吧。。。。
    huanyouchen
        24
    huanyouchen  
       2018-06-30 20:43:57 +08:00
    通过字典构建一个哈希表:
    class Solution:
    def twoSum(self, nums, target):
    dic = {}
    for i,num in enumerate(nums):
    if num in dic:
    return [dic[num],i]
    else:
    dic[target-num] = i
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1600 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 16:57 · PVG 00:57 · LAX 08:57 · JFK 11:57
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.