Leetcode 1. Two Sum

https://leetcode.com/problems/two-sum/

The key step is converting the process of trying every number to finding if there is such a number, which can be done with Python's ‘in’ statement. Actually extra space is needed, and the complexity is T:O(n) S:O(n).

Why do we need extra space? If we search in the rest of list, the time complexity is actually O(n^2)! Sometimes we have to sacrifice space for time. So we just create a dictionary to do it.

Also, we can sort the numbers, and find the two indexes from head and tail. But this solution the sort process will spend more time than the search process, so it is not as good as the first one.

Solution 1:

# T:O(n) S:O(n)
class Solution:
    # @param {integer[]} nums
    # @param {integer} target
    # @return {integer[]}
    def twoSum(self, nums, target):
        dict = {}
        for i in nums:
            if target - nums[i] in dict:
                return [dict[target - nums[i]] + 1, i + 1]
            dict[nums[i]] = i 

Run Time: 48 ms

Solution 2:

# T:O(nlgn) S:O(n)
class Solution:
    # @param {integer[]} nums
    # @param {integer} target
    # @return {integer[]}
    def twoSum(self, nums, target):
        n = sorted(nums)
        head, tail = 0, len(nums) - 1
        while head < tail:
            if n[head] + n[tail] == target:
                p1, p2 = nums.index(n[head]), nums.index(n[tail])
                if p1 == p2:
                    p2 = nums[p1+1:].index(n[tail]) + p1 + 1
                return [min(p1+1, p2+1), max(p1+1, p2+1)]
            elif n[head] + n[tail] > target:
                tail -= 1
            elif n[head] + n[tail] < target:
                head += 1 

Run Time: 48 ms