1.Two Sum

Posted on | In

Question：

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.

Example：

1
2
3
4
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

My First answer: (wrong)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        j=0
        for i in nums:
            j+=1
            tmp=nums[j:]
            if target-i in tmp:
                return [nums.index(i),nums.index(target-i)]
        return [0,0]
1
2
3
input:(3,3)
output(0,0)
should be(0,1)

so we need to clear the index and value, exchange their position to make them uniqueness

Modified Answer:

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        d={}
        for i,value in enumerate(nums):
            if target-value in d:
                return [d[target-value],i]
            d[value]=i

Traverse the list, and put every item into the list d, and the order of return list is also important, first is index in list d, because the item in list d is earilier put from the origin list i.e. list nums. Second is current index in list nums.

Complexity Analysis：

  • Time complexity：O (n)，for each element , we try to find its complement by looping through the rest of array which takes O (n) time
  • Space complexity：O (1)

Supplement:

List

list1 = ['physics', 'chemistry', 1997, 2000]

list.append(x) : Add an item x to the end of the list

list.extend(list) : Extend the list by appending all the items in the given list

list.insert(i,x)

list.remove(x) : the first item from the first

list.pop([i]) : Remove the item at the given position in the list, and return it

list.index(x)

list.count(x)

list.sort()

list.reverse()

del(list[2])

len(list)

cmp(list1,list2)

max(list),min(list)

['Hi']*4

3 in [1,2,3]

for x in [1,2,3]

list[2] : the third item in the list

list[-2] : the second last item in the list

list[1:] : read the list beginning from the second item

enumerate(sequence, [start=0]) ()

1
2
for index, value in enumerate(list):
    print(index, value)