Medium

题目描述

给定一个链表的头结点，链表中包含唯一的整数值，以及一个整数数组 nums，该数组是链表值的一个子集。

返回 nums 中连通组件的个数，其中两个值连通当且仅当它们在链表中连续出现。

示例 1：

输入：head = [0,1,2,3], nums = [0,1,3]
输出：2
解释：0 和 1 是连通的，所以 [0, 1] 和 [3] 是两个连通组件。

示例 2：

输入：head = [0,1,2,3,4], nums = [0,3,1,4]
输出：2
解释：0 和 1 是连通的，3 和 4 是连通的，所以 [0, 1] 和 [3, 4] 是两个连通组件。

提示：

  • 链表中节点的数量为 n
  • 1 <= n <= 10^4
  • 0 <= Node.val < n
  • 所有 Node.val 的值都是唯一的
  • 1 <= nums.length <= n
  • 0 <= nums[i] < n
  • nums 的所有值都是唯一的

解题思路

解题思路

这道题的关键在于理解什么是"连通组件"：如果 nums 中的两个值在链表中相邻，则它们属于同一个连通组件。

核心思路：

  1. 首先将 nums 数组转换为哈希集合，便于 O(1) 时间查找
  2. 遍历链表，统计连通组件的起始点个数
  3. 当前节点值在 nums 中且前一个节点值不在 nums 中时，说明找到了一个新的连通组件的开始

算法步骤：

  • 使用哈希集合存储 nums 中的所有值
  • 遍历链表，对每个节点：
    • 如果当前节点值在集合中，且前一个节点值不在集合中（或为空），则连通组件数量加1
    • 这样可以确保每个连通组件只被计算一次

优化点：

  • 只需要判断连通组件的起始位置，避免重复计算
  • 时间复杂度为 O(n)，空间复杂度为 O(m)，其中 n 是链表长度，m 是 nums 数组长度

代码实现

class Solution {
public:
    int numComponents(ListNode* head, vector<int>& nums) {
        unordered_set<int> numSet(nums.begin(), nums.end());
        int components = 0;
        bool inComponent = false;
        
        while (head) {
            if (numSet.count(head->val)) {
                if (!inComponent) {
                    components++;
                    inComponent = true;
                }
            } else {
                inComponent = false;
            }
            head = head->next;
        }
        
        return components;
    }
};

class Solution:
    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:
        num_set = set(nums)
        components = 0
        in_component = False
        
        while head:
            if head.val in num_set:
                if not in_component:
                    components += 1
                    in_component = True
            else:
                in_component = False
            head = head.next
        
        return components

public class Solution {
    public int NumComponents(ListNode head, int[] nums) {
        HashSet<int> numSet = new HashSet<int>(nums);
        int components = 0;
        bool inComponent = false;
        
        while (head != null) {
            if (numSet.Contains(head.val)) {
                if (!inComponent) {
                    components++;
                    inComponent = true;
                }
            } else {
                inComponent = false;
            }
            head = head.next;
        }
        
        return components;
    }
}

var numComponents = function(head, nums) {
    const numSet = new Set(nums);
    let components = 0;
    let inComponent = false;
    
    while (head) {
        if (numSet.has(head.val)) {
            if (!inComponent) {
                components++;
                inComponent = true;
            }
        } else {
            inComponent = false;
        }
        head = head.next;
    }
    
    return components;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n + m)n 为链表长度，m 为 nums 数组长度。创建哈希集合需要 O(m)，遍历链表需要 O(n)
空间复杂度O(m)哈希集合存储 nums 中的所有元素

相关题目