写点什么

LeetCode 热题一之两数之和

作者:Hunter熊
  • 2025-07-27
    北京
  • 本文字数:1139 字

    阅读完需:约 4 分钟

LeetCode热题一之两数之和

本文首发于公众号: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)}
复制代码


发布于: 刚刚阅读数: 3
用户头像

Hunter熊

关注

公众号:Hunter后端 2018-09-17 加入

Python后端工程师,欢迎互相沟通交流

评论

发布
暂无评论
LeetCode热题一之两数之和_Python_Hunter熊_InfoQ写作社区