Leetcode刷题-1.两数之和-Go/Python

使用嵌套for循环

时间复杂度为O()，最坏的情况下数组中任意2个元素都要匹配一次。

空间复杂度为O(1)，只用到常数个临时变量。

运行结果：

func twoSum(nums []int, target int) []int {
    arrlen := len(nums)
    for i := 0;i < arrlen ;i++{
		for j := i+1;j < arrlen ;j++{
            if nums[i] + nums[j] == target{
                resp := []int{i, j}
                return resp
            }
        }
	}
    return nil 
}

运行结果：

def twosum(nums, target):
    listLen = len(nums)
    for i in range(0, listLen):
        for j in range(i+1, listLen):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

优化思路

• 遍历时记录一些信息，以省去一次遍历。以空间换时间。
• 记录已遍历的值和下标，可借助查找表实现。
• 每次遍历，x为遍历的元素。判断target - x的值是否在查找表中，如果存在则返回此值的下标和当前元素下标。

运行结果：

func twoSum(nums []int, target int) []int {
    arrlen := len(nums)
    var map1 = make(map[int]int)                    //创建一个Map
    for i := 0;i < arrlen ;i++{
//判断Map中是否存在target-num[i]的key。存在则返回key的下标和当前元素下标；不存在则将当前元素和下标存入Map
        if _, ok := map1[target - nums[i]]; ok {    
            return []int{map1[target - nums[i]], i}
        }
        map1[nums[i]] = i
	}
    return nil 
}

运行结果：

def twosum(nums, target):
    listlen = len(nums)
    dicttmp = {}
    for i in range(0, listlen):
        if target - nums[i] in dicttmp:
            return [dicttmp[target - nums[i]], i]
        dicttmp[nums[i]] = i
    return []