target = i + (target - i) , you can select one element and see if any other element which can be combined target.
You can use the following code to do the search, but this will take linear time to do so, which will exceed the time limit in this problem.
for i in range(len(num)): if not target - num(i) in num:
Therefore, using dictionary for search is the alternative way, which only take constant time for search.
The full code as below,
class Solution: # @return a tuple, (index1, index2) def twoSum(self, num, target): dict_num = dict() for i in num: dict_num[i] = 1 for i in range(len(num) - 1): if not target - num[i] in dict_num: continue for j in range(i + 1, len(num)): if num[i] + num[j] == target: return i + 1, j + 1
Well... I don't know how to estimate the time complexity yet.
Is it O(n) or O(nlogn)?
class Solution: # @return a tuple, (index1, index2) def twoSum(self, num, target): dict_num = dict.fromkeys(num,0) for i in range(len(num) - 1): if not target - num[i] in dict_num: continue try : return i + 1, i+2+num[i+1:].index(target - num[i]) except : continue
With your help, I finally AC this problem.And here is my version.And below is another one,also using dict(), but slower:
class Solution : def twoSum(self,num,target): Dic = dict() n = 1 for i in num : Dic[i] = n n += 1 Len = len(num) + 1 while True: Len -= 1 A = num.pop() try : B = Dic[target - A] if Len == B : continue C = [Len,B] C.sort() return tuple(C) except : continue