算法题解：两数之和

淩亂°似流年 2023-07-12 14:42 18阅读 0赞

### 题目 ###

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

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

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

因为 nums\[0\] + nums\[1\] = 2 + 7 = 9  
所以返回 \[0, 1\]

题目来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/two-sum

### 解答 ###

package main
    
    import "fmt"
    
    func main() {
    	arr := []int{3, 2, 6, 11, 9, 16}
    
    	//fmt.Println(twoSum2(arr, 15))  // [2,4]
    	//fmt.Println(twoSum(arr, 18)) // [1,5]
    	//fmt.Println(twoSum(arr, 13)) // [1,3]
    	//fmt.Println(twoSum(arr, 17)) // [2,3]
    	//fmt.Println(twoSum(arr, 27)) // [3,5]
    	//fmt.Println(twoSum(arr, 50)) // []
    
    	fmt.Println(twoSum2(arr, 15)) // [2,4]
    	fmt.Println(twoSum2(arr, 18)) // [1,5]
    	fmt.Println(twoSum2(arr, 13)) // [1,3]
    	fmt.Println(twoSum2(arr, 17)) // [2,3]
    	fmt.Println(twoSum2(arr, 27)) // [3,5]
    	fmt.Println(twoSum2(arr, 50)) // []
    }
    
    // 姿势1
    func twoSum(nums []int, target int) []int {
    	count := len(nums)
    	var resArr []int
    	for i := 0; i < count; i++ {
    		for j := i + 1; j < count; j++ {
    
    			if nums[i]+nums[j] == target {
    				resArr = append(resArr, i, j)
    				return resArr[:]
    			}
    		}
    	}
    
    	return resArr[:]
    }
    
    // 姿势2
    func twoSum2(nums []int, target int) []int {
    	count := len(nums)
    	resMap := make(map[int]int)
    	var resArr []int
    	for i := 0; i < count; i++ {
    		num2 := target - nums[i]
    		if _, ok := resMap[num2]; ok {
    			resArr = append(resArr, resMap[num2], i)
    			return resArr
    		}
    
    		resMap[nums[i]] = i
    	}
    
    	return resArr[:]
    }

###  ###