LeetCode双指针与哈希技巧解决面试高频题

本资源主要介绍了三个经典的LeetCode算法题目，涉及字符串反转、前K个高频元素和两个数组的交集II问题，这些题目都是面试时常被考察的基础技巧。 1. 反转字符串 (LeetCode 344) - 题目要求通过双指针法实现字符串s的反转。定义两个指针i和j，初始时i指向字符串开头，j指向结尾。当i小于j时，交换s[i]和s[j]的值，直到i和j相遇。此操作体现了数组操作的基本技巧，用于处理字符串或数组的对称性质。 ```cpp void reverseString(vector<char>& s) { int n = s.size(); for (int i = 0, j = n - 1; i < j; i++, j--) { swap(s[i], s[j]); } } ``` 2. 前K个高频元素 (LeetCode 347) - 这道题要求找出数组中出现频率最高的前k个元素。首先，通过计数排序的方式统计每个元素出现的次数，存储在unordered_map cnt中。接着，计算出现次数大于等于第k高频率元素下界的索引i。最后，遍历cnt，将出现次数大于等于i的元素添加到结果数组res中。 ```cpp vector<int> topKFrequent(vector<int>& nums, int k) { // ... int i = n, t = 0; while (t < k) t += s[i--]; // 找到k的下界 // ... } ``` 3. 两个数组的交集II (LeetCode 350) - 本题要求找出两个整数数组nums1和nums2中的公共元素，但不考虑重复元素。通过哈希表（unordered_map）实现，首先遍历nums1，更新哈希表cnt的元素计数。然后遍历nums2，若元素x在哈希表中存在，将其添加到结果数组res并减少计数。最后返回不重复的公共元素res。 ```cpp vector<int> topKFrequent(vector<int>& nums, int k) { unordered_map<int, int> cnt; // ... vector<int> res; for (auto& p : cnt) { if (p.second > i) res.push_back(p.first); } return res; } ``` 这些题目展示了数据结构和算法在实际编程中的应用，包括双指针策略、计数排序以及哈希表的使用。理解和掌握这些问题有助于提升在面试中解决类似问题的能力，同时也是对基础算法熟练度的检验。