哈希
1. 两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
提示：
2 <= nums.length <= 104-109 <= nums[i] <= 109-109 <= target <= 109- 只会存在一个有效答案
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
// 排序 + 双指针 left right
// 思路类似于二分法，通过控制区间范围找目标
// 补充：要求返回下标，如果引入排序会打乱下标
// 解决方案，引入副本，对副本进行排序，在原本中获取下标
unordered_set<int> res;
vector<int> sortedNums = nums;
sort(sortedNums.begin(), sortedNums.end());
// 左闭右闭
int left = 0;
int right = nums.size()-1;
// 终止条件：左闭右闭，左 == 右时，区间元素为空集
while(left < right){// 找到了，处理结果
int sum = sortedNums[left] + sortedNums[right];
if(sum == target){
//在原本中获取下标
for(int i = 0;i < nums.size(); i++){
if(nums[i]==sortedNums[left]){
res.insert(i);
}
}
for(int i = nums.size()-1; i >= 0; i--){
if(nums[i]==sortedNums[right]){
res.insert(i);
}
}
return vector<int>(res.begin(), res.end());
}else if(sum > target){
// 太大了，右侧往左缩（前提：已排序）
right--;
}else if(sum < target){
// 太小了，左侧往右扩（前提：已排序）
left++;
}
}
return {};
}
};
49. 字母异位词分组
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
示例 1:
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
示例 2:
输入: strs = [""]
输出: [[""]]
示例 3:
输入: strs = ["a"]
输出: [["a"]]
提示：
1 <= strs.length <= 1040 <= strs[i].length <= 100strs[i]仅包含小写字母
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
//声明哈希表
unordered_map<string, vector<string>> hashTable;
//生成哈希表
for(string str:strs){
//关键：字母异位词排序后结果相同
//排序后作 key，排序前作 value
//key 对应 value 数组就是字母异位词组合
string key = str;
sort(key.begin(), key.end());
hashTable[key].push_back(str);
}
//遍历哈希表获取结果
vector<vector<string>> res;
for(auto it = hashTable.begin(); it != hashTable.end(); it++ ){
res.push_back(it->second);
}
return res;
}
};
128. 最长连续序列
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1：
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
示例 2：
输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9
提示：
0 <= nums.length <= 105-109 <= nums[i] <= 109
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
//引入集合，用于去重，避免相同数字重复计算
unordered_set<int> set(nums.begin(), nums.end());
int res = 0;
for(int num:nums){
//当前数字
if(set.count(num) > 0){
set.erase(num);
//初始化相邻数字
int pre = num - 1, next = num + 1;
//左相邻数字存在，删除左相邻数字，并向左外延
while(set.count(pre)>0){
set.erase(pre--);
}
//右相邻数字存在，删除右相邻数字，并向右外延
while(set.count(next)>0){
set.erase(next++);
}
//更新结果
res = max(res, next - pre - 1);
}
}
return res;
}
};
双指针
283. 移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
示例 2:
输入: nums = [0]
输出: [0]
提示:
1 <= nums.length <= 104-231 <= nums[i] <= 231 - 1
class Solution {
public:
void moveZeroes(vector<int>& nums) {
//快慢双指针（一前一后）
int left = 0, right = 1;
//避免快指针越界
while(right < nums.size()){
//实操 + 真值表：
//左 0 右 0，快指针右移
//左 0 右 非0，交换
//左非0，左右指针均右移
if(nums[left]==0){
if(nums[right]==0)
right++;
else
swap(nums[left], nums[right]);
}else{
left++;
right++;
}
}
}
};
11. 盛最多水的容器
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。
示例 1：
输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
示例 2：
输入：height = [1,1]
输出：1
提示：
n == height.length2 <= n <= 1050 <= height[i] <= 104
class Solution {
public:
//类似于两数之和
int maxArea(vector<int>& height) {
//首尾双指针，左闭右闭
int left = 0, right = height.size()-1;
int maxRes = 0;
// 终止条件：左闭右闭，左 == 右时，区间元素为空集
while(left < right){
//短板效应：最短高度限制最大面积
int tmpHeight = min(height[left], height[right]);
maxRes = max(maxRes, tmpHeight * (right - left));
//更新短板，保证全扫描
if(height[left] < height[right]){
//左柱子为短板，则左指针右移
left++;
}else{
//右柱子为短板，则右指针左移
right--;
}
}
return maxRes;
}
};