Leetcode Solutions（一） two-sum

來自專欄 萌新的學習日記Leetcode Solutions（一） two-sum?

zhangslob.github.io

Two Sum

題目

給定一個整數數組和一個目標值，找出數組中和為目標值的兩個數。

你可以假設每個輸入只對應一種答案，且同樣的元素不能被重複利用。

示例:

給定 nums = [2, 7, 11, 15], target = 9因為 nums[0] + nums[1] = 2 + 7 = 9所以返回 [0, 1]

解題思路

Go

a + b = target

也可以看成是

a = target - b

在map[整數]整數的序號中，可以查詢到a的序號。這樣就不用嵌套兩個for循環了。

func twoSum(nums []int, target int) []int { m := make(map[int]int, len(nums)) for i, b := range nums { if j, ok := m[target-b]; ok { return []int{j, i} } m[nums[i]] = i } return nil}

Python

1. 由於要找到符合題意的數組元素的下標，所以先要將原來的數組深拷貝一份，然後排序。

1. 然後在排序後的數組中找兩個數使它們相加為target。這個思路比較明顯：使用兩個指針，一個指向頭，一個指向尾，兩個指針向中間移動並檢查兩個指針指向的數的和是否為target。如果找到了這兩個數，再將這兩個數在原數組中的位置找出來就可以了。

1. 要注意的一點是：在原來數組中找下標時，需要一個從頭找，一個從尾找，要不無法通過。如這個例子：numbers=[0,1,2,0]; target=0。如果都從頭開始找，就會有問題。

class Solution: def twoSum(self, nums, target): if len(nums) <= 1: return False d = dict() for i in range(len(nums)): if nums[i] in d: return [d[nums[i]], i] else: d[target - nums[i]] = i