一、编程题：75. 颜色分类（双指针，循环不变量）
1.题目描述
给定链表头结点 head，该链表上的每个结点都有一个 唯一的整型值 。同时给定列表 nums，该列表是上述链表中整型值的一个子集。返回列表 nums 中组件的个数，这里对组件的定义为：链表中一段最长连续结点的值（该值必须在列表 nums 中）构成的集合。LeetCode题目链接。
2.示例1：
输入: head = [0,1,2,3], nums = [0,1,3]
输出: 2
解释: 链表中,0 和 1 是相连接的，且 nums 中不包含 2，所以 [0, 1] 是 nums 的一个组件，同理 [3] 也是一个组件，故返回 2。
3.示例2：
输入：输入: head = [0,1,2,3,4], nums = [0,3,1,4]
输出: 2
解释: 链表中，0 和 1 是相连接的，3 和 4 是相连接的，所以 [0, 1] 和 [3, 4] 是两个组件，故返回 2。
4.提示：
- 链表中节点数为n
- 1 <= n <= 104
- 0 <= Node.val < n
- Node.val 中所有值 不同
- 1 <= nums.length <= n
- 0 <= nums[i] < n
- nums 中所有值 不同
二、解题思路
这里一定要注意题干的要求，链表跟数组都是无序的（本人被坑过）。
1.思路
解决方法1（个人想法）：
- Step1.用while循环遍历链表head，再根据head.val来判定是否存在nums数组中；
- Step2.用循环来判定head.val是否在nums中，当head.val == nums[i]时，则将head.val置为-1表示存在，并结束循环；
- Step3.处理完链表之后，再对链表中的-1结点进行计算，这里设置flag=0（当flag为0时，表示该结点的数据再nums里是不存在的，反之为1表示存在）；
- Step4.当head.val != -1且flag == 1时，说明该结点之前的数为一个组件；当head.val == -1时，则flag=1，这里要考虑到当前结点为边界结点，组件数count要加1；
解决方法2（哈希表）：
在前面的基础上引入HashSet集合，加快查询的速度，这里不用ArraysList的原因是hashSet查询比较快。
- Step1.创建HashSet集合来存储数组；
- Step2.（循环1）遍历链表head，当head.val存在于set中时，则进入循环2判断下一个结点是否存在，当下一个结点不存在时，结束循环2，组件数count+1；反之当head.va不l存在于set中则指向下一个结点即可；
三、代码实现
。每个代码块都写了注释，方便理解，代码还可以改进；
代码如下（示例）：
解法一：
class Solution { public int numComponents(ListNode head, int[] nums) { //方法一 int count = 0, flag = 0; //组件个数 ListNode left = head; ListNode result = head; while(left != null){ for(int i = 0; i < nums.length; i++){ if(nums[i] == left.val){ left.val = -1; break; } } left = left.next; } while(result != null){ if(result.val != -1 && flag == 1){ // System.out.println(result.val); count++; flag = 0; }else if(result.val == -1){ // System.out.println("=>"+result.val); flag = 1; if(result.next == null) count++; } result = result.next; } return count; } }
解法二：
class Solution { public int numComponents(ListNode head, int[] nums) { //方法二 int count = 0; HashSet<Integer> set = new HashSet<>(); for(int number : nums) set.add(number); while (head != null){ if(set.contains(head.val)){ head = head.next; //这里可以减少一次不必要的循环 while(head != null && set.contains(head.val)) head = head.next; count++; }else{ head = head.next; } // 遍历链表：只有当前节点元素值在nums中且当前节点下一个节点值不在nums中时，才能作为1个独立组件 // if(set.contains(head.val) && (head.next == null || !set.contains(head.next.val))) count++; // head = head.next; } return count; } }
提交结果：
总结
以上就是今天要讲的内容，一开始做题的时候，刚开始写的时候，没有想到用hashSet来加快查询速度，于是用了两个while，搞得非常冗余，思路上也有待提升，看了三叶姐代码之后，发现可以用hashSet来加速判断，也感受到了三叶姐思路的清晰感，自己写的时候都是边写边错边改，所以就赶紧记录一下这个方法，开阔一下思路。
感谢观看，如果有帮助到你，请给题解点个赞和收藏，让更多的人看到。🌹 🌹 🌹
也欢迎你，关注我。👍 👍 👍
原创不易，还希望各位大佬支持一下，你们的点赞、收藏和留言对我真的很重要！！！💕 💕 💕 最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！
