LeetCode-题目1 两数之和实现思路与提升

题目链接:https://leetcode-cn.com/problems/two-sum/

题目描述:

两数之和
两数之和

大家最简单想到的就是暴力破解,嵌套循环遍历数组:

#golang实现
#小细节 遍历前取出数组长度避免每次循环时,数组都去重新获取长度,外次循环循环至倒数第二个数即可
func twoSum(nums []int, target int) []int {
    length:=len(nums)
    for i:=0;i<length-1;i++{
        for j:=i+1;j<length;j++{
            if nums[i]+nums[j]==target{
                return []int{i,j}
            }
        }
    }
    return []int{0,0}
}
#python3实现
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        for i in range(n):
            for j in range(i + 1, n):
                if nums[i] + nums[j] == target:
                    return [i, j]    
        return []

上述解法为大家普遍能想到的解法,下边给大家提供一种golang利用哈希表只需遍历一次数组的解法(其他语言可根据思路实现):

func twoSum(nums []int, target int) []int {
    //声明一个map key存数组中的值与目标值的差,value为值对应的索引
    hashTable := map[int]int{}
    //遍历数组
    for i, x := range nums {
        //取数组中当前值与目标的差值,若存在返回当前索引和对应的差值的索引
        if p, ok := hashTable[target-x]; ok {
            return []int{p, i}
        }
        //map对象中不存在,则将数组中的值符给map供后边的值判断使用
        hashTable[x] = i
    }
    return nil
}

感兴趣的同学可以关注此博客,大家一起交流进步!