作者Kuba4ma ()
看板Python
标题[问题] leecode167 Time Limit Exceeded
时间Wed Mar 18 17:43:14 2020
题目
Given an array of integers that is already sorted in ascending order, find
two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they
add up to the target, where index1 must be less than index2.
Note:
Your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution and you may
not use the same element twice.
Example:
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.
code:
class Solution(object):
def twoSum(self, numbers, target):
"""
:type numbers: List[int]
:type target: int
:rtype: List[int]
"""
answer=list()
length=len(numbers)
for i in range(length):
for j in range(i+1,length):
if numbers[i]+numbers[j]==target:
answer.append(i+1)
answer.append(j+1)
return answer
问题:
runcode没问题，但submit会Time Limit Exceeded，是leecode没办法接受时间复杂度太高
的答案吗?
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 117.19.168.127 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Python/M.1584524596.A.25A.html
1F：推 yushes920179: 纯回答你问题 是 03/18 18:32
2F：推 cuteSquirrel: 对，Time Complexity太高。 03/18 19:12
3F：推 cuteSquirrel: 提示:O(n)演算法、利用以排序的性质、double index 03/18 19:15
4F：→ cuteSquirrel: 已排序 03/18 19:15
5F：推 jn8029: 讨论区有O(n)的解法啊 03/19 09:57
6F：推 cuteSquirrel: 对，讨论区upvote按赞数高的解法，很值得一读。 03/19 13:35