本文首發於公眾號：Hunter後端

原文鏈接：LeetCode熱題一之兩數之和

題目

給定一個整數數組 nums 和一個整數目標值 target，請你在該數組中找出和為目標值 target 的那兩個整數，並返回它們的數組下標。

你可以假設每種輸入只會對應一個答案，並且你不能使用兩次相同的元素。

你可以按任意順序返回答案。

題目來源

此題來源於 LeetCode 題庫序號 1。

LeetCode 鏈接

示例

示例 1

輸入：nums = [2,7,11,15], target = 9

輸出：[0,1]

解釋：因為 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2

輸入：nums = [3,2,4], target = 6

輸出：[1,2]

示例 3

輸入：nums = [3,3], target = 6

輸出：[0,1]

題解

對於這道題，要在一個數組中找兩個元素，使得他們的和為目標值 target，第一反應是需要雙重遍歷數組，第一重挨個遍歷數組元素作為第一個值，第二重是從該元素往後開始遍歷作為第二個值，判斷這兩個值之和是否等於目標值。

其偽代碼大致如下：

for i in range(len(nums) - 1):
    for j in range(i + 1, len(nums)):
        if nums[i] + nums[j] == target:
            return 

但是這個操作需要雙重遍歷數組，其時間複雜度為 n^2，因此，可以尋求一個時間複雜度更小的做法。

我們可以額外建立一個哈希表，key 為元素，value 為元素的索引，每次遍歷到的元素 x 可以先查一下哈希表看 target-x 是否存在，存在的話説明我們已經找到了兩個目標元素，不存在的話就將元素 x 存入表中。

以下是偽代碼：

itemDict = {}
for i in range(len(nums) - 1):
    item = nums[i]
    if itemDict.get(target - item) != None:
        return [itmDict[target-item], i]
    else:
        itemDict[x] = 1

代碼

Python 代碼

from typing import List


class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        itemDict = dict()
        for i, item in enumerate(nums):
            if itemDict.get(target - item) != None:
                return [itemDict[target-item], i]
            else:
                itemDict[item] = i
        return [-1, -1]


nums = [2,7,11,15]
target = 9

result = Solution().twoSum(nums, target)
print(result)

Golang 代碼

package main

import "fmt"

func twoSum(nums []int, target int) []int {
    itemMap := map[int]int{}
    for i, item := range nums {

        if originItem, exists := itemMap[target-item]; exists {
            return []int{originItem, i}
        } else {
            itemMap[item] = i
        }
    }
    return []int{}
}

func main() {
    nums := []int{2, 7, 11, 15}
    target := 9
    result := twoSum(nums, target)
    fmt.Println(result)
}