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
复杂度
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次循环匹配
复杂度
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个指针分别向中间收缩
复杂度
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]
}
}
