two sum问题(-)

前言

两数之和问题，简而言之就是从数组中找到两个数的和等于某个特定的值，考察的主要思想是空间换时间。同时它还有许多变种，如三数之和、四数之和问题。

题目集合

two sum及其变种如下：

题目 难度等级 备注
two sum easy
Two Sum II - Input array is sorted easy
Two Sum III - Data structure design easy 要订阅，暂时放弃。。。
Subarray Sum Equals K medium
Two Sum IV - Input is a BST easy
Two Sum Less Than K easy

1、经典原题: two sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

解法一：暴力破解

1
2
3
4
5
6
7
8
9
10
func twoSum(nums []int, target int) []int {
    for i := 0; i < len(nums); i++ {
        for j := i + 1; j < len(nums); j++ {
            if nums[i]+nums[j] == target {
                return []int{i, j}
            }
        }
    }
    return nil
}

runtime distribution

Runtime: 36 ms, faster than 31.90% of Go online submissions for Two Sum.

memory distribution

Memory Usage: 3 MB, less than 100.00% of Go online submissions for Two Sum.

思考

暴力破解是最容易想到的方法，它的时间复杂度是O(n^2)。虽然很多时候我们都对暴力解法嗤之以鼻，但是从上面的时间分布和内存分布看，优点还是很明显的，即内存消耗很小。

在计算机里面，增加内存的成本远远小于提高计算能力的成本，所以我们需要考虑如何通过空间来换时间。

解法二：哈希表法

1
2
3
4
5
6
7
8
9
10
11
12
13
func twoSum(nums []int, target int) []int {
    var numsMap = make(map[int]int)
    for i := 0; i < len(nums); i++ {
        numsMap[nums[i]] = i
    }
    for i := 0; i < len(nums); i++ {
        j, ok := numsMap[target - nums[i]]
        if ok && j != i {
            return []int{i, j}
        }
    }
    return nil
}

runtime distribution

Runtime: 4 ms, faster than 95.00% of Go online submissions for Two Sum.

memory distribution

Memory Usage: 3.8 MB, less than 11.54% of Go online submissions for Two Sum.

如果把代码中numsMap的定义改成：

1
var numsMap = make(map[int]int, len(nums))

memory distribution

Memory Usage: 3.4 MB, less than 42.31% of Go online submissions for Two Sum.

思考

暴力解法中，比较耗时的操作是第二个for循环，第二个for循环的作用是判断第二个数加第一个数是不是等于目标值，这是一个凑数的过程。如果我们反过来想，在已知第一个数的情况下，判断我们需要找的数是不是在剩下的数的集合里面，时间复杂度就变成了O(1)。

从时间分布看，超过了95%的人(说明还能继续优化)；从内存分布看，只超过了11.54%的人。但是如果在初始化numsMap的时候指定了长度，消耗的内存就会少0.4M，由此可见，Go中map类型数据指定长度初始化是有必要的。

这里面需要注意的是，如果数组中有两个元素一致，那哈西表中存的索引就是第二个元素的索引值。但是因为我们是从前往后遍历的，所以结果不影响。至于有三个及以上的元素相同的情况是不用考虑的，因为题目说只有唯一解。

解法三：哈希表法升级版

1
2
3
4
5
6
7
8
9
10
func twoSum(nums []int, target int) []int {
    numsMap := make(map[int]int, len(nums))
    for i, v := range nums {
        if pre, ok := numsMap[target - v]; ok {
            return []int{pre, i}
        }
        numsMap[v] = i
    }
    return nil
}

runtime distribution

Runtime: 4 ms, faster than 95.00% of Go online submissions for Two Sum.

memory distribution

Memory Usage: 3.4 MB, less than 48.08% of Go online submissions for Two Sum.

思考

解法二中，出现了两个遍历，一次是numsMap赋值的时候，一次是查找的时候。但实际上这两次是可以合并的，即一边赋值，一边查找。

至于为什么runtime排名还是小于95%，应该是网站的bug，时间最少的那个人的耗时是0ms，显然不可能。测试发现，如果重复提交多次，有可能出现这种情况。

2、变种一：Two Sum II - Input array is sorted

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.

Note:

Your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution and you may not use the same element twice.

Examples

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func twoSum(numbers []int, target int) []int {
    i := 0
    j := len(numbers) - 1
    
    for i < j {
        if numbers[i] + numbers[j] == target {
            return []int{i+1, j+1}
        } else if numbers[i] + numbers[j] > target {
            j--
        } else {
            i++
        }
    }
    return nil
}

思考

这个变种比较简单，数据按升序排好，只需要使用双指针，向中间靠拢即可

变种二：Two Sum IV - Input is a BST

Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.

Example:

1
2
3
4
5
6
7
8
9
10
Input: 
    5
   / \
  3   6
 / \   \
2   4   7

Target = 9

Output: True

解法一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func findTarget(root *TreeNode, k int) bool {
	list := printTree(root)
	hashSet := make(map[int]int)
	for i := 0; i < len(list); i++ {
		except := k - list[i]
		if hashSet[except] == 1 {
			return true
		}
        hashSet[list[i]] = 1
	}
	return false
}

/**
 * 层序遍历
 */
func printTree(root *TreeNode) []int {
	queue := make([]*TreeNode, 0)
	queue = append(queue, root)
	list := make([]int, 0)
	for len(queue) > 0 {
		list = append(list, queue[0].Val)
		left := queue[0].Left
		right := queue[0].Right
		if left != nil {
			queue = append(queue, left)
		}
		if right != nil {
			queue = append(queue, right)
		}
		queue = queue[1:]
	}
	return list
}

Runtime distribution

Runtime: 24 ms, faster than 86.52% of Go online submissions for Two Sum IV - Input is a BST.

memory distribution

Memory Usage: 7.6 MB, less than 50.00% of Go online submissions for Two Sum IV - Input is a BST.

思考

通过层序遍历，将二叉搜索树转成数组，然后再通过哈希表法判断是否存在两个数的和等于目标值

解法二

1

leetcode

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！