美文网首页leetcode
1. leetcode python twosum

1. leetcode python twosum

作者: ciantian | 来源:发表于2017-10-21 10:16 被阅读12次

    最近再刷leetcode,用python 实现,贴出一些代码,希望指正.

    问题描述:Given an array of integers, return indices of the two numbers such that they add up to a specific target.
    You may assume that each input would have exactly one solution, and you may not use the same element twice.
    给定一个整数列表,和一个目标数字,返回列表中和为目标数字的下标.
    样例输入:Given nums = [2, 7, 11, 15], target = 9,
    Because nums[0] + nums[1] = 2 + 7 = 9,
    return [0, 1].

    算法思想:
    step1 加上索引排序.
    step2 用折半查找算法
    step3 返回的时候复原以前的索引.

    class Solution:
        def twoSum(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: List[int]
            """
            list2 = list(zip([x for x in range(len(nums))], nums))
            list3 = sorted(list2, key=lambda x: x[1])
    
            def bin_search(list1, var):
                low = 0
                hight = len(list1) - 1
                while low <= hight:
                    mid = (low + hight) // 2
                    if list1[mid][1] == var:
                        return list1[mid][0]
                    elif list1[mid][1] > var:
                        hight = mid - 1
                    else:
                        low = mid + 1
                return -1
            length = len(list3)
            for i in range(length-1):
                j = bin_search(list3[i+1:],target-list3[i][1])
                if j!=-1:
                    return [list3[i][0],j]
    solution = Solution()
    nums2 = [3, 2, 3]
    print(solution.twoSum(nums2, 6))
    
    

    相关文章

      网友评论

        本文标题:1. leetcode python twosum

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