LeetCode 986. 区间列表的交集

Categories:

Tags:

题目描述
思路分析
参考代码

题目描述

✅ 986. 区间列表的交集

思路分析

双指针

参考代码

func intervalIntersection(A [][]int, B [][]int) [][]int {
	res := [][]int{}
	i, j := 0, 0
	for i < len(A) && j < len(B) {
		// 找到交集的起始和结束
		start := max(A[i][0], B[j][0])
		end := min(A[i][1], B[j][1])

		// 如果有交集
		if start <= end {
			res = append(res, []int{start, end})
		}

		// 移动指针
		if A[i][1] < B[j][1] {
			i++
		} else {
			j++
		}
	}
	return res
}

时间复杂度：O (n + m)，其中 n 和 m 分别是两个区间列表的长度。

空间复杂度：O (k)，其中 k 是结果中交集的数量。

func intervalIntersection(A [][]int, B [][]int) [][]int {
    var res [][]int
    i, j := 0, 0

    // 遍历 A 和 B
    for i < len(A) && j < len(B) {
        // 如果有交集
        if A[i][1] >= B[j][0] && B[j][1] >= A[i][0] {
            // 交集区间为 [max(A[i][0], B[j][0]), min(A[i][1], B[j][1])]
            res = append(res, []int{max(A[i][0], B[j][0]), min(A[i][1], B[j][1])})
        }

        // 移动指针
        if A[i][1] < B[j][1] {
            i++
        } else {
            j++
        }
    }

    return res
}

时间复杂度：O(m + n)，其中 m 和 n 分别是 A 和 B 的长度。

空间复杂度：O(min(m, n))，即最多保存两个数组的交集部分。

➡️ 点击查看 Java 题解

write your code here

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/71305127