leetcode: 两数之和

题目：

作者：gpe3DBjDS1
链接：https://leetcode-cn.com/problems/two-sum/solution/liang-shu-zhi-he-by-gpe3dbjds1/
来源：力扣（LeetCode）

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

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

示例: 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]

解答：

• 方法1

func twoSum(nums []int, target int) []int {
    result := make([]int, 2)
    
    for i := 0; i < len(nums); i++ {
        tmpValue := nums[i]
        tmpIndex := i
        
        for index, value := range nums {
            if tmpIndex == index || index < tmpIndex {
                continue
            }
        
            sum := tmpValue + value
            if sum == target {
                result[0] = tmpIndex
                result[1] = index
                return result
            } 
        } 
    }
    
    return result
}

缺点：耗时长
特点：时间换空间

• 方法2

func twoSum(nums []int, target int) []int {
    result := make([]int, 0)
    
    for i := 0; i < len(nums) - 1; i++ {
        for j := i +1; j < len(nums); j++ {
            sum := nums[i] + nums[j]
            if sum == target {
                result = append(result, i, j)
                return result
            }
        }
    }
    
    return result
}

缺点：耗时长，相比方法1耗时要短
特点：时间换空间

• 方法3

func twoSum(nums []int, target int) []int {
    tmp := make(map[int]int, len(nums))
    result := make([]int, 0)

    for index, value := range nums {
        tmp[value] = index
    }

    for index, value := range nums {
        diffValue := target - value
        if diffIndex, ok := tmp[diffValue]; ok {
            if diffIndex == index {
                continue
            }

            result = append(result, index, diffIndex)
            return result
        }
    }

    return result
}

缺点：内存消耗较方法1和方法2大
特点：执行时间缩短，空间换时间

• 方法4

func twoSum(nums []int, target int) []int {
    result := make([]int, 0)

    tmp := make(map[int]int, len(nums))
    for index, value := range nums {
        diffValue := target - value
        if diffIndex, ok := tmp[diffValue]; ok {
            result = append(result, diffIndex, index)
            return result
        }

        tmp[value] = index
    }

    return result
}

缺点：内存消耗较方法1、2、3都大
特点：执行速度快，空间换时间