哈希表

两个链表的第一个重合节点 原题链接：https://leetcode.cn/problems/3u1WK4/ 给定两个单链表的头节点 headA 和 headB ，请找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。 图示两个链表在节点 c1 开始相交： 题目数据 保证 整个链式结构中不存在环。 函数返回结果后，链表必须 保持其原始结构 。 1.哈希表主要思路： 遍历listA将其中的结点全部标记存入unset中（哈希表） 遍历listB直到其中出现相同的next域的值 直接返回其值即为结果 若遍历listB都完都没有出现符合要求的结果则返回nullptr 1234567891011121314151617181920//注：将unordered_set放到成员方法内部可以提高时间效率class Solution {public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { unordered_set<ListNode*> unset; //1.initialize unset ListNode* tmp = headA; while (tmp) { unset.insert(tmp); tmp = tmp->next; } //2.find the first node tmp = headB; while (tmp) { if (unset.count(tmp)) return tmp; tmp = tmp->next; } return nullptr; }}; 时间：48ms 内存：16.24mb 时间复杂度：$O(N)$ 空间复杂度：$O(N)$ 2.双指针主要思路： 首先判断链表是否为空，如果其中有一个链表为空则两个链表一定不相交返回nullptr 当链表都不为空时 创建两个指 ...

链表中环的入口节点 原题链接：https://leetcode.cn/problems/c32eOV/ 给定一个链表，返回链表开始入环的第一个节点。 从链表的头节点开始沿着 next 指针进入环的第一个节点为环的入口节点。如果链表无环，则返回 null。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。 注意 pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。 说明：不允许修改给定的链表。 1.哈希表思路： 利用哈希表建立一个标记数组 用于标记已经出现的next指针域 while循环遍历链表 直到出现重复的next指针域 表示链表环开始出现 返回此时的链表结点指针 即为环入口结点 unordered_map1234567891011121314class Solution {public: unordered_map<ListNode*, int> mark; ListNode *detectCycle(ListNode *head) { if (head == nullptr) return nullptr; ListNode* p = head; while (p) { if (mark[p]) return p; mark[p] = 1; p = p->next; } return nullptr; }}; 时间：12ms 内存：9.8mb unordered_set12345678910111213public: unordered_set<ListNode*> mark; ListNode *detectCycle(ListNode *head) { if (head == nullptr) return nullptr; ListNode* p = head; while (p) { if (mark. ...

不含重复字符的最长子字符串 原题链接：https://leetcode.cn/problems/wtcaE1/ 给定一个字符串 s ，请你找出其中不含有重复字符的 最长连续子字符串 的长度。 1.静态滑动窗口11

字符串中的变位词 原题链接：https://leetcode.cn/problems/MPnaiL/ 给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的某个变位词。第一个字符串的排列之一是第二个字符串的 子串 。 1.静态滑动窗口1由于知道目标字符串的长度，故可以通过暴力枚举的方式（一个静态的滑动窗口）来枚举出所有的情况， 并对枚举的每种情况进行字母数量的统计，利用哈希表实现字母数量的统计， 123456789101112131415class Solution {public: bool checkInclusion(string pattern, string text) { for (int i = 0, j = i + pattern.length(); j <= text.length(); ++i, ++j) { int flag = 0; vector<int> cnt(26); for (int k = 0; k < pattern.length(); ++k) cnt[pattern[k] - 'a']++;//查找目标的字母数量统计 for (int k = i; k < j; ++k) cnt[text[k] - 'a']--;//遍历的字符串的字母数量统计 for (int i = 0; i < 26; ++i) if (cnt[i] != 0) flag = 1;//判断字母数量是否相同 if (flag) continue; return true; } return false; }}; 勉强能过，时间复杂度与空间复杂度都很高。 2.静态滑动窗口2对每次的字母数量判断操作进行修改，对边界值进行加入与减出操作，思路没有问题的，先做记录在此。 1234567891011121314151617181920212223class Solution {public ...

字符串中的所有变位词 原题链接：https://leetcode.cn/problems/VabMRr/ 给定两个字符串 s 和 p，找到 s 中所有 p 的 变位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。 变位词 指字母相同，但排列不同的字符串。 1.静态滑动窗口11

0和1个数相同的子数组 原题链接：https://leetcode.cn/problems/A1NYOS/ 给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。 1.暴力枚举123456789101112131415class Solution {public: int findMaxLength(vector<int>& nums) { int ans = 0; for (int j = 0; j < nums.size(); ++j) { int sum = 0; for (int i = j; i >= 0; --i) { if (nums[i] == 1) sum++; else sum--; if (sum == 0) ans = max(ans, j - i + 1); } } return ans; }}; 程序超时，看来这题对时间复杂度的要求很高，需要牺牲空间复杂度换时间复杂度降低。 2.前缀和+哈希 在预处理前缀和时，将 nums[i] 为 0 的值当做 −1 处理 从而将问题转化为：如何求得最长一段区间和为 0 的子数组，使用哈希表来记录某个前缀和出现的最小下标是多少。 12345678910111213141516171819202122class Solution {public: int findMaxLength(vector<int>& nums) { int ans = 0; int len = nums.size(); //1.前缀和数组初始化 int *prefix = new int[len + 10](); for (int i = 1; i <= nums.size(); ++i) prefix[i] = pref ...

和为k的子数组 原题链接：https://leetcode.cn/problems/QTMn0o/ 给定一个整数数组和一个整数 k ，请找到该数组中和为 k 的连续子数组的个数， 1.静态滑动窗口1遍历滑动窗口大小，每次for循环滑动窗口大小值固定，每次对滑动窗口中的内容进行求和，尝试更新答案，时间超时： 1234567891011121314class Solution {public: int subarraySum(vector<int>& nums, int k) { int ans = 0; for (int len = 1; len < nums.size(); ++len) { for (int i = 0, j = i + len; j <= nums.size(); ++i, ++j) { int sum = 0; for (int n = i; n < j; ++n) sum += nums[n]; if (sum == k) ans++; } } return ans; }}; 所有用例成功输出结果，但由于时间复杂度太高，导致程序超时， 2.静态滑动窗口2遍历滑动窗口大小，每次for循环滑动窗口大小值固定， 维护一个sum值 进行加入与减出，每次窗口移动加入与减出边界值，尝试更新答案： 1234567891011121314151617class Solution {public: int subarraySum(vector<int>& nums, int k) { int ans = 0; for (int len = 1; len <= nums.size(); ++len) { int sum = 0; for (int i = 0; i < len; ++i) sum += n ...

只出现一次的数字 原题链接：https://leetcode.cn/problems/WGki4K/description/ 给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。 1.暴力法1234567891011121314151617class Solution {public: int singleNumber(vector<int> &nums) { vector<int> ans = nums; sort(ans.begin(), ans.end()); ans.erase(unique(ans.begin(), ans.end()), ans.end()); for (int i = 0; i < ans.size(); ++i) { int count = 0; for (int j = 0; j < nums.size(); ++j) { if (nums[j] == ans[i]) count++; if (count > 1) break; } if (count == 1) return ans[i]; } return -1; }}; 2.哈希法哈希法：哈希映射统计数组中每个元素的出现次数，在统计完成后，遍历哈希映射即可找出只出现一次的元素。 12345678910111213141516class Solution {public: int singleNumber(vector<int>& nums) { int ans = 0; unordered_map<int, int> unmap; for (int num : nums) unmap[num]++; pair<i ...

两数之和 原题链接：https://leetcode.cn/problems/two-sum/ 给定一个整数数组nums和一个整数目标值target，请你在该数组中找出和为目标值target的那两个整数，并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返回答案。 1.暴力法1234567891011121314class Solution {public: vector<int> twoSum(vector<int>& nums, int target) { int i, j; for (i = 0; i < nums.size(); ++i) { for (j = i + 1; j < nums.size(); ++j) { if (nums[i] + nums[j] == target) { return {i, j}; } } } return {i, j}; }}; 2.二分查找思想：sort排序 + 二分查找 使用for循环遍历数组中的每一个数字 在for循环内部，使用target值减去当前遍历的数字值获取配对值ret，使用二分查找该数字ret 如果找到该数字则直接输出其下标(初始若有序的情况下) 实际是无序的！难点在于如何联系被sort打乱下标后的vec与未打乱的nums，并从其中找出目标数字的下标？ 1234for (int j = 0; j < n; j++) { if (nums[j] == vec[i] || nums[j] == ret) result.push_back(j); if(result.size() == 2) return result;} 12345678910111213141516171819202122 ...