leetcode-1 两数之和

留言

难度: 中等


最朴素的一种解法,两次循环~时间复杂度为O(n的平方)

直接贴代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
func twoSum(nums []int, target int) []int {
 
    rs := make([]int,0)
    for i,v := range nums {
        for i2,v2 := range nums{
            if v + v2 == target && i != i2 {
                rs = append(rs,i,i2)
                return rs
            }     
        }
    }
    return rs
}


进一步优化时间复杂度,用空间换时间
两次一维循环,时间复杂度为O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func twoSum(nums []int, target int) []int {
	hash := make(map[int]int)

	for k, v := range nums {
		hash[v] = k
	}

	for k, v := range nums {
		tmp := target - v

		if _, ok := hash[tmp]; ok {
			if hash[tmp] == k {
				continue//"你不能重复利用这个数组中同样的元素",防止如目标值为6,数组为[3,2,4]这种情况下[0,0]也符合条件
			}
			return []int{k, hash[tmp]}

		}
	}

	return nil

}



***

还可以继续优化为一次一维循环,时间复杂度为O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func twoSum(nums []int, target int) []int {
	hash := make(map[int]int)

	for k,v := range nums {
		if j,ok := hash[target-v];ok {
			return []int{k,j}

		}

		hash[v] = k
	}


	return nil

}



文章目录