0817. 链表组件【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 哈希表

1. 📝 题目描述

• leetcode

给定链表头结点 head，该链表上的每个结点都有一个 唯一的整型值。同时给定列表 nums，该列表是上述链表中整型值的一个子集。

返回列表 nums 中组件的个数，这里对组件的定义为：链表中一段最长连续结点的值（该值必须在列表 nums 中）构成的集合。

示例 1：

输入: head = [0,1,2,3], nums = [0,1,3]
输出: 2
解释: 链表中,0 和 1 是相连接的，且 nums 中不包含 2，所以 [0, 1] 是 nums 的一个组件，同理 [3] 也是一个组件，故返回 2。

示例 2：

输入: head = [0,1,2,3,4], nums = [0,3,1,4]
输出: 2
解释: 链表中，0 和 1 是相连接的，3 和 4 是相连接的，所以 [0, 1] 和 [3, 4] 是两个组件，故返回 2。

---

提示：

• 链表中节点数为n
• 1 <= n <= 10^4
• 0 <= Node.val < n
• Node.val 中所有值 不同
• 1 <= nums.length <= n
• 0 <= nums[i] < n
• nums 中所有值 不同

2. 🎯 s.1 - 哈希表

c

int numComponents(struct ListNode* head, int* nums, int numsSize) {
    bool set[10001] = {false};
    for (int i = 0; i < numsSize; i++) set[nums[i]] = true;
    int res = 0;
    bool inComp = false;
    while (head) {
        if (set[head->val]) {
            if (!inComp) { res++; inComp = true; }
        } else {
            inComp = false;
        }
        head = head->next;
    }
    return res;
}

js

/**
 * @param {ListNode} head
 * @param {number[]} nums
 * @return {number}
 */
var numComponents = function (head, nums) {
  const set = new Set(nums)
  let res = 0,
    inComp = false
  let cur = head
  while (cur) {
    if (set.has(cur.val)) {
      if (!inComp) {
        res++
        inComp = true
      }
    } else {
      inComp = false
    }
    cur = cur.next
  }
  return res
}

py

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

• 时间复杂度：$O(n)$，其中 n 是链表长度
• 空间复杂度：$O(m)$，其中 m 是 nums 的长度

算法思路：

• 将 nums 放入哈希集合，遍历链表统计连续在集合中的片段数