TalkGo 算法之美第一期题解

• 完整题解地址

题目 - 和为 S 的两个数字

题目描述

输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。

可以用数学证明一个最小的数和最大的数的乘积是最小的

样例

案例 1:

输入: nums = {1, 2, 4, 7, 11, 15}, s = 15 
输出: {4, 11}

案例 2:

输入: nums = {1, 2, 4, 7, 11, 16}, s = 17 
输出: {1, 16}

案例 3:

输入: nums = {1, 2, 4, 7, 11, 16}, s = 10 
输出: {}

案例 4:

输入: nums = {1, 2, 4, 7, 8, 11, 15}, s = 10 
输出: {4, 11}
有4+11=15和7+8=15两组解，因为 4*11=44 < 7*8=56, 所以就题解是 {4, 11}

题解1：穷举

思路：2次循环穷举所有case

复杂度

• 时间复杂度：O(N^2)
• 可能复杂度：O(1)

Code

func Solution(nums []int, s int) []int {
	ans := []int{}
	for i := 0; i < len(nums); i++ {
		for j := len(nums) - 1; j > 0; j-- {
			if nums[i]+nums[j] == s {
				ans = append(ans, []int{nums[i], nums[j]}...)
				goto End
			}
		}
	}
End:
	return ans
}

题解2：hash map

思路：建立一个 key =nums[i], val = idx 的 map, 第二次2次循环匹配

复杂度

• 时间复杂度：O(N)
• 可能复杂度：O(N)

Code

func Solution(nums []int, s int) []int {
	m, ans := make(map[int]int), []int{}
	for i, num := range nums {
		m[num] = i
	}
	for _, num := range nums {
		if _, ok := m[s-num]; ok {
			ans = append(ans, []int{num, s - num}...)
			break
		}
	}
	return ans
}

题解3：双指针

思路：左右2个指针分别向中间收缩

复杂度

• 时间复杂度：O(N^2)
• 可能复杂度：O(1)

Code

func Solution(nums []int, s int) []int {
	left, right, ans := 0, len(nums)-1, []int{}
	for left < right {
		if nums[left]+nums[right] > s {
			right -= 1
		} else if nums[left]+nums[right] < s {
			left += 1
		} else {
			ans = append(ans, []int{nums[left], nums[right]}...)
			break
		}
	}
	return ans
}

题目 - 求中位数

题目描述

一个有序数组，从随机一位截断，把前段放在后边，如 4 5 6 7 1 2 3 求中位数

样例

案例 1:
输入 nums = {1, 2, 3, 7, 11, 15}
输出 5
{1, 2, 3, 4, 5, 6, 7} 从 4 开始折断 

案例 2:
输入 nums = {7, 11, 15, 1, 2, 3}
输出 5

案例 2:
输入 nums = {7, 11, 15, 1, 2, 3, 4}
输出 4

题解1：排序

思路：排序后直接计算

复杂度

• 时间复杂度：时间复杂度：O (LogN)
• 可能复杂度：O(N^2)

Code

func Solution(nums []int) int {
	sort.Ints(nums)
	n := len(nums)
	//	偶数
	if n%2 == 0 {
		return (nums[n/2] + nums[n/2-1]) / 2
	//	奇数
	} else {
		return nums[n/2]
	}
}