LeetCode 1. 两数之和

xiaoXingcode-go / 2023-05-07 / 原文

题目链接：LeetCode 1. 两数之和

题意：

本题就是要找出数组中的两个数，使得它们的和等于target

解题思路：

1、首先暴力的做法就是两层的for循环，遍历整个nums数组，找出所有的组合，判断组合中是否有相加等于target的组合

算法复杂度为O(n^2) ,

代码如下：

// 暴力解法
func twoSum(nums []int, target int) []int {
    for k1, _ := range nums {
        for k2 := k1 + 1; k2 < len(nums); k2++ {
            if target == nums[k1] + nums[k2] {
                return []int{k1, k2}
            }
        }
    }
    return []int{}
}

2、可以采用逆向的思维，既然两个数的总和知道了，那么如果知道其中一个数，那么另一个数也就是知道了，

此时，判断该数是否在nums数组中，即可得到该组合是否成立

代码如下：

func twoSum(nums []int, target int) []int {
    // 首先暴力的做法就是两层的for循环，遍历整个nums数组，找出所有的组合，判断组合中是否有相加等于target的组合
    // 算法复杂度为O(n^2)

    // 可以采用逆向的思维，既然两个数的总和知道了，那么如果知道其中一个数，那么另一个数也就是知道了，
    // 此时，判断该数是否在nums数组中，即可得到该组合是否成立

    set := make(map[int]int) //声明一个map,key是数组的值，value是数组的下标
    for i,v :=range nums{   
         set[v] = i+1   //标记所有出现过的数字，将下标+1的值存到map中
    }
    var res []int
    for i,_ :=range nums{
        tmp := target - nums[i]   
        if set[tmp] > 0  && i != set[tmp]-1{   //如果 target - nums[i] 这个数出现过，同时不和nums[i]是同一个数，则就是答案 (题干中表明：只有一组按，并且同一个元素不能重复出现)
            res= append(res,[]int{i,set[tmp]-1}...)
            break
        } 
    }
    return res
}

优化一下：

// 使用map方式解题，降低时间复杂度
func twoSum(nums []int, target int) []int {
    m := make(map[int]int)
    for index, val := range nums {
        if preIndex, ok := m[target-val]; ok {
            return []int{preIndex, index}
        } else {
            m[val] = index
        }
    }
    return []int{}
}