算法学习-求两数之和

本文来源吾爱破解论坛

TIM截图20181116171104.png (27.28 KB, 下载次数: 1)

下载附件  保存到相册

题目内容

2018-11-21 10:04 上传

解题思路:
题目本身难度不大,难度大的地方在于时间限制和python知识
最开始想到的方法就是双层循环,求和判断.但是这个方法在最后一个例子测试的时候超时了(我本地i7需要10秒时间)
然后查了一下list的方法,发现有一个index函数,可以求值在队列中的序号
那么可以先排序,再处理.因为是排过序了,所以只要和大于target了,就可以终止循环,进一步提高时间了
[Python] 纯文本查看 复制代码

class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        cacls = nums[:]
        cacls.sort()
        for i in range(len(cacls) - 1):
            for j in range(i + 1, len(cacls)):
                if cacls[i] + cacls[j] == target:
                    head = nums.index(cacls[i])
                    tail = nums.index(cacls[j])
                    if head == tail:
                        tail = nums.index(cacls[j], head + 1)
                    ret = [head, tail]
                    ret.sort()
                    return ret
                if cacls[i] + cacls[j] > target:
                    break
        return []