1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public int numComponents(ListNode head, int[] nums) {
Set<Integer> subset = new HashSet<>();
for (int num : nums) {
subset.add(num);
}
int ans = 0;
ListNode ptr = head;
while (ptr != null) {
int count = 0;
while (ptr != null && subset.contains(ptr.val)) {
count += 1;
ptr = ptr.next;
}
if (count >= 1) {
ans += 1;
} else {
ptr = ptr.next;
}
}
return ans;
}
}
|
先把nums存到set里面, 然后我们就开始遍历链表即可. 用一个count来记录用多少个combo. combo连击大于等于1的时候, 我们让ans + 1. 如果combo是0, 说明当前的node不在set中, 我们更新ptr即可.
时间复杂度: O(n) n是list的长度. 我们把nums中的元素装入set需要O(n), 遍历list需要O(n)
空间复杂度: O(n) n是list的长度, 因为我们用了set.
