Leetcode 1/167. Two Sum

Posted on | | 阅读数
Words count in article: 206 | Reading time ≈ 1

Question1

Solution1

首先，题目要求同一个数据不能使用两次，并且只有一个解。所以考虑将第i个元素和其后面的所有元素遍历求和，如果没有发现，则i+1。

1
2
3
4
5
6
7
8
9
10
class Solution:
    def twoSum(self, nums: 'List[int]', target: 'int') -> 'List[int]':
        for i in range(len(nums) - 1):
            j = i + 1
            while j < len(nums):
                if nums[i] + nums[j] == target:
                    return i, j
                else:
                    j += 1
		return

Solution2

考虑用字典来储存配对，方便后面搜索。

1
2
3
4
5
6
7
8
9
10
class Solution:
    def twoSum(self, nums: 'List[int]', target: 'int') -> 'List[int]':
        dic = {}
        for i in range(len(nums)):
            n = nums[i]
            if n not in dic:
                dic[target-n] = i
            else:
                return [dic[n], i]
        return []

Question2

Solution

同样的方法解。

1
2
3
4
5
6
7
8
9
10
class Solution:
    def twoSum(self, nums: 'List[int]', target: 'int') -> 'List[int]':
        dic = {}
        for i in range(len(nums)):
            n = nums[i]
            if n not in dic:
                dic[target-n] = i
            else:
                return [dic[n]+1, i+1]
        return []