# 两数之和 (题1)
---
:::success

给定一个整数数组nums 和一个目标值target，请你在该数组中找出和为目标值的那两个整数，

并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

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

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

:::

- **1. 暴力解法**
:::success

// 时间复杂度 n*n
func twoSum(nums []int, target int) []int {
	length := len(nums)

	result := make([]int, 0)
    
	if length < 2 {
		return result
	}

	for i := 0; i < length; i++ {
		for j := i + 1; j < length; j++ {
			if nums[i] + nums[j] == target {
				result = append(result, i, j)
				return result
			}
		}
	}

	return result
}

:::

- **2. 两次遍历哈希表**
:::success

// 时间复杂 O(n)
func twoSum(nums []int, target int) []int {
	maps := make(map[int]int, 0) // 记得使用之前要先初始化，不然会抛异常

	result := make([]int, 0)
    
    length := len(nums)
	if length < 2 {
		return result
	}

	for key, value := range nums {
		maps[value] = key
	}

	//然后在map中寻找符合target的要求的值
	for i, v := range nums {
        // 同样的元素不能被重复利用，记得注意不能是自己本身
		if _, ok := maps[target - v]; ok && maps[target - v] != i { 
			result = append(result, i, maps[target - v])
			break
		}
	}

	return result
}

:::

- **3. 1次遍历哈希表**
:::success

// 时间复杂度O(n)
func twoSum(nums []int, target int) []int {
	maps := make(map[int]int, 0)

	result := make([]int, 0)

	length := len(nums)

	if length < 2 {
		return result
	}

	for key, value := range nums {
		if i, ok := maps[target - value]; ok {
			//如果找到，直接return下标
			result = append(result, i, key)
			break
		}
		//没有找到储存到map
		maps[value] = key
	}

	return result
}

:::

###### tags: `LeeCode`