題目

給定兩個由一些 閉區間 組成的列表，firstList 和 secondList ，

其中 firstList[i] = [starti, endi] 而 secondList[j] = [startj, endj] 。

每個區間列表都是成對 不相交 的，並且 已經排序 。

返回這 兩個區間列表的交集 。

形式上，閉區間 [a, b]（其中 a <= b）表示實數 x 的集合，而 a <= x <= b 。

兩個閉區間的 交集 是一組實數，要麼為空集，要麼為閉區間。例如，[1, 3] 和 [2, 4] 的交集為 [2, 3] 。

示例 1：輸入：firstList = [[0,2],[5,10],[13,23],[24,25]],

secondList = [[1,5],[8,12],[15,24],[25,26]]

輸出：[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

示例 2：輸入：firstList = [[1,3],[5,9]], secondList = [] 輸出：[]

示例 3：輸入：firstList = [], secondList = [[4,8],[10,12]] 輸出：[]

示例 4：輸入：firstList = [[1,7]], secondList = [[3,10]] 輸出：[[3,7]]

提示：0 <= firstList.length, secondList.length <= 1000

firstList.length + secondList.length >= 1

0 <= starti < endi <= 109

endi < starti+1

0 <= startj < endj <= 109

endj < startj+1

解題思路分析

1、雙指標；時間複雜度O(n)，空間複雜度O(1)

func intervalIntersection(A [][]int, B [][]int) [][]int {	res := make([][]int, 0)	i, j := 0, 0	for i < len(A) && j < len(B) {		if A[i][0] <= B[j][1] && B[j][0] <= A[i][1] {			left := max(A[i][0], B[j][0])			right := min(A[i][1], B[j][1])			res = append(res, []int{left, right})		}		if A[i][1] < B[j][1] {			i++		} else {			j++		}	}	return res}func max(a, b int) int {	if a > b {		return a	}	return b}func min(a, b int) int {	if a > b {		return b	}	return a}

2、雙指標；時間複雜度O(n)，空間複雜度O(1)

func intervalIntersection(A [][]int, B [][]int) [][]int {	res := make([][]int, 0)	i, j := 0, 0	for i < len(A) && j < len(B) {		left := max(A[i][0], B[j][0])		right := min(A[i][1], B[j][1])		if left <= right {			res = append(res, []int{left, right})		}		if A[i][1] < B[j][1] {			i++		} else {			j++		}	}	return res}func max(a, b int) int {	if a > b {		return a	}	return b}func min(a, b int) int {	if a > b {		return b	}	return a}

總結

Medium題目，陣列有序，使用雙指標，判斷重複區間即可