1. 两数之和

easy

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

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

两重循环

时间复杂度 O(n^2^)，空间复杂度 O(1)

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
func twoSum(nums []int, target int) []int {
    for i,num1:=range nums{
        for j,num2:=range nums[i+1:]{
            if num1+num2==target{
                return []int{i,j+i+1}
            }
        }
    }
    return nil
}

哈希表

键为数组中各元素的值，哈希表的值为数组中该值出现的位置

在哈希表中是否存在 target - nums[i] 的键，若存在则说明这两数相加结果为 target，返回结果。

1
2
3
4
5
6
7
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        d={}
        for i,num in enumerate(nums):
            if target-num in d.keys(): 
                return [i,d[target-num]]
            d[num]=i

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
func twoSum(nums []int, target int) []int {
    prevNums := map[int]int{}
	for i, num1 := range nums {
		num2 := target - num1
		j, ok := prevNums[num2]
		if ok {
			return []int{j, i}
		} else {
			prevNums[num1] = i
		}
	}
	return []int{}
}