跟着LeetCode的Study Plan重温一遍各种经典算法，本期是二分搜索算法Level1 Day10。
题目构成：Easy*1 + Medium*1。
大概就是返回两个数组的交集，数组的元素可能重复，代码(Golang)如下：
func intersect(nums1 []int, nums2 []int) []int {
sort.Ints(nums1)
sort.Ints(nums2)
l1, l2 := len(nums1), len(nums2)
var shortNums, longNums []int
if l1 > l2 {
shortNums = nums2
longNums = nums1
} else {
shortNums = nums1
longNums = nums2
}
l3 := len(longNums)
helper := func(_s int, _e int, _t int) int {
_i, _j := _s, _e
for _i <= _j {
_m := (_i + _j) / 2
_v := longNums[_m]
if _v >= _t {
_j = _m - 1
} else {
_i = _m + 1
}
}
_p := _j + 1
if _p < l3 && longNums[_p] == _t {
return _p
}
return -1
}
start := 0
var r []int
for _, n := range shortNums {
p := helper(start, l3-1, n)
if p != -1 {
start = p + 1
r = append(r, n)
}
}
return r
}
这道题用map做很简单，但为了练习还是使用的二分法：
1. 先对两个数组排序
2. 遍历短的数组，二分搜索长的数组，以优化性能
3. helper函数使用二分在_s ~ _e范围内查找第一个目标值的位置，如果未找到就返回-1
4. 找到目标值之后添加到结果slice里，下一次二分从更新后的start开始，避免每次搜索整个数组
判断一个int是否等于两个int的平方和，代码(Golang)如下：
func judgeSquareSum(c int) bool {
half := int(math.Sqrt(float64(c)))
for i := 0; i < half+1; i++ {
j := c - i*i
_a, _b := 0, j
for _a <= _b {
_m := (_a + _b) / 2
_v := _m * _m
if _v == j {
return true
} else if _v > j {
_b = _m - 1
} else {
_a = _m + 1
}
}
}
return false
}
这道题直接用开方的函数做简单一些。