LeetCode热题100 【cpp】题解（一）哈希表和双指针

题单链接： LeetCode 热题 100

1. 两数之和

leetcode题目链接
题解1：暴力枚举
时间复杂度：$O(n^2)$

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {vector<int> v;for (int i = 0; i < nums.size() - 1; i ++) {for (int j = i + 1; j < nums.size(); j ++) {if (nums[i] + nums[j] == target) {v.push_back(i), v.push_back(j);}}}return v;}
};

题解2：哈希表
时间复杂度：$O(n)$

使用hash表来存target - x的差值的下标。这里使用cpp里面的unordered_map，它的查找效率为$O(1)$

补充unordered_map 查找key的方法：count()， 如果存在某个key, 返回1；如果不存在某个key，返回0.

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> heap; // heap存 <差值， 下标>for (int i = 0; i < nums.size(); i ++) {int r = target - nums[i];if (heap.count(r)) { // count方法判断key存不存在return {heap[r], i};}heap[nums[i]] = i; // 记录这个数的下标}return {};}
};

49. 字母异位词分组

leetcode题目链接

题解：
字母异位词的意思是某些字符串含有相同的字母，并且每个字母出现的次数相同。字母异位词也可以理解为字符串排完序之后完全相同。

本题解利用后者（排序）进行处理：如果两个字符串是字母异位词，那么它们排完序之后一定相同。可以使用哈希表来维护一个string的vector，记录排完序相同的字符串。时间瓶颈是在排序上，排序的复杂度是$nlogn$。
时间复杂度：$O(nlogn)$

class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {unordered_map<string, vector<string>> hash;for(auto& str: strs) {string nstr = str; // nstr为排序过后的新字符串sort(nstr.begin(), nstr.end());hash[nstr].push_back(str);}vector<vector<string>> res;for(auto& item: hash) {res.push_back(item.second);}return res;}
};

128. 最长连续序列

leetcode题目链接

题解：哈希表
我们每次从一个序列的最小值开始枚举，如果是连续的，迭代器不停++。比如最小值是x，那么其后是x+1, x+2, …, y，那么该连续序列的长度是多少呢？是y - x +1 这么长。为了加快查找速度，我们将所有元素存入哈希表unordered_set S中。还有一个问题，如何确定一个序列的开始呢？ 如果哈希表S中存在x，不存在x - 1，那么我们就说x是一个序列的开始。

补充
unordered_set这个hash表，会将元素去重，并且不会排序，可以通过元素的值快速检索出该元素。
时间复杂度：$O(n)$

class Solution {
public:int longestConsecutive(vector<int>& nums) {unordered_set<int> S;// 构造hash表：将所有元素插入到set中for(auto x: nums) S.insert(x);int res = 0;for(auto x : S) {// 枚举序列的最小值xif(S.count(x) && !S.count(x - 1)) {int y = x;// 如果是连续的序列，y一直++while(S.count(y + 1)) {y ++;}res = max(res, y - x + 1); // 更新序列长度}}return res;}
};

283. 移动零

leetcode题目链接
题解：双指针

前一个指针x从头开始遍历数组，后一个指针k保存非零元素，k从零开始，逐渐加1。当所有的非零元素都移动到前面之后，此时k指向第一个零的位置，从此往后枚举补零即可。

时间复杂度：$O(n)$

class Solution {
public:void moveZeroes(vector<int>& nums) {int k = 0; // k是后一个指针，用于存放非零的数for (auto x : nums) {if (x) {nums[k] = x;k ++;}}// 把数组后面的位置补零while (k < nums.size()) {nums[k] = 0;k ++;}}
};

11. 盛最多水的容器

leetcode题目链接
题解：双指针
两个指针i 和 j形成的水槽的面积由短板决定，面积计算公式如下:
$$S=min(h[i],h[j])\ast (j-i)$$

每个状态下，两个指针i和j向中间移动一格，都会使得底边变短，怎样才能使得面积变大呢？
只有每次把短板向中间靠拢，它向中间靠拢才可能使矩形的高变高，面积才能变大。因为下一个状态的高度可能比短板高。移动的过程中，每次记录下来面积的最大值。参考 leetcode题解

时间复杂度：$O(n)$

class Solution {
public:int maxArea(vector<int>& height) {int res = 0;for (int i = 0, j = height.size() - 1; i < j;) {res = max(res, min(height[i], height[j]) * (j - i));// 每次短边向中间移动if (height[i] < height[j]) i ++;else j --;}return res;}
};

15. 三数之和

leetcode题目链接

题解：排序 + 双指针

对数组从小到大排序。开始遍历数组，第一个下标 $i$ 表示三个数中的第一个，我们固定这个数，然后使用双指针算法(枚举$j和k$)找到另外两个数，使得$nums[i]+nums[j]+nums[k]\ge 0,i<j<k$,同时使得k尽可能的小（k是最后一个指针，指向三数中的最大值，从右往左移动）。在上述情况中找到三数之和等于0的情况。

另外，需要确保没有枚举出来重复的情况，比如 $nums=[-1,-1,-1,-1,2]$，怎样才能做到只出现一次$[-1,-1,2]$？在枚举的时候如果出现 $nums[i]==nums[i-1]$，我们就跳过，直接$i$++, 直到$nums[i]\ne nums[i-1]$。$nums[j]$同理。

时间复杂度：$O(n^2)$，排序是$O(nlogn),$ 外层循环$（i）$是$O(n)$, 内层双指针循环$j和k$ 是$O(n)$，相乘是$O(n^2)$。

参考题解：acwing题解

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> res;if (nums.size() < 3) return res;sort(nums.begin(), nums.end());for (int i = 0; i < nums.size(); i ++) {if (i > 0 && nums[i] == nums[i - 1]) continue;// 双指针：j是头指针，k是尾指针，两者向中间靠拢for (int j = i + 1, k = nums.size() - 1; j < k; j ++) {if (j > i + 1 && nums[j] == nums[j - 1]) continue;// 找到3数之和 ≥ 0 的最小的位置， k是3数之和≥0的最前面的位置while (j < k - 1 && nums[i] + nums[j] + nums[k - 1] >= 0) k --;if (nums[i] + nums[j] + nums[k] == 0)res.push_back({nums[i], nums[j], nums[k]});}}return res;}
};

42. 接雨水

leetcode题目链接

题解：双指针，计算总面积 - 陆地面积。计算总面积时是每行的面积进行累加。
数组求和使用cpp中的accumulate函数。
参考题解：接雨水

class Solution {
public:int trap(vector<int>& height) {int length = height.size();if (length < 3) return 0;int l = 0, r = length - 1;// 前一次计算时的高度int preHeight = 0;// 陆地 + 雨水的总面积int totalArea = 0;// 陆地面积：数组所有数求和int landArea = 0;// accumulate 是cpp累加函数landArea = accumulate(height.begin(), height.end(), 0);while (l < r) {while (l < r && height[l] <= preHeight) l ++;while(l < r && height[r] <= preHeight) r --;// 每一层的面积：高度差 x 宽度totalArea += (min(height[l], height[r]) - preHeight) * (r - l + 1);preHeight = min(height[l], height[r]);}return totalArea - landArea;}
};