哈希模块
哈希结构：
哈希结构，即hash table，哈希表|散列表结构。
图摘自《代码随想录》
哈希表本质上表示的元素和索引的一种映射关系。
若查找某个数组中第n个元素，有两种方法：
1.从头遍历，复杂度：O(n)
2.使用数组这种hash结构，根据下标(索引)来查找，复杂度：O(1)
实现了快速判断元素是否出现在集合里。
哈希函数：
哈希函数指：根据映射关系，构造hash表的方法
哈希碰撞： 当根据映射方法进行映射，构造hash表时，出现两个元素抢占一个索引的现象，叫做hash碰撞。
如：hash函数 index=(value%3)
则0和3所得索引都是0，抢占同一索引0，发生hash碰撞。
解决hash碰撞的两个方法：拉链法和线性探测：
拉链法:将冲突的元素串成链表，放在被抢占的索引处。
线性探测：将一个元素放入该索引，顺找该索引往下找一个空位置，存放另一个元素。
Leetcode 1. 两数之和
题意理解：
给定一个整数数组
nums和一个整数目标值target，请你在该数组中找出 和为目标值target的那 两个 整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。
给定一个数组，和一个目标值target, 求数组中两个数和为target, 这两个数的下标。
解题思路：
采用hash结构来解题，目的是快速找到某个值
哈希法解题：
public int[] twoSum(int[] nums, int target) {
Map<Integer,Integer> numsMap=new HashMap<>();
for(int i=0;i<nums.length;i++){
if(!numsMap.isEmpty()&&numsMap.keySet().contains(nums[i])){
return new int[]{i,numsMap.get(nums[i])};
}
numsMap.put(target-nums[i],i);
}
return null;
}复杂度分析：
时间复杂度：O(n), 遍历数组的开销
空间复杂度：O(n), hash表的开销
Leetcode 49. 字母异位词分组
题意理解：
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
字母异位词本质上是元素一样的数组。
则所有异位字符串，通过字母按从小到大的顺序重排，得到的值是一样的。我们将其作为索引，对应字母异位词，本质上是哈希表的拉链法。
解题思路：
将异位字符串，通过字母按从小到大的顺序重排，得到的值作为index
通过map进行收集index和以为字符串的映射关系。
主要是依赖了哈希结构：index和value的对应关系。
哈希解题：
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, ArrayList<String>> map=new HashMap<>();
for(int i=0;i< strs.length;i++){
String index=recombination(strs[i]);
if(map.containsKey(index)){
map.get(index).add(strs[i]);
}else {
ArrayList<String> newList=new ArrayList<>();
newList.add(strs[i]);
map.put(index,newList);
}
}
return new ArrayList<>(map.values());
}
public String recombination(String str){
char[] strArr=str.toCharArray();
Arrays.sort(strArr);
return String.valueOf(strArr);
}复杂度分析：
时间复杂度：O(nklogk), 遍历元素的时间n，每个元素排序的世家klogk
空间复杂度：O(nk), 字符数组的大小
n是元素个数，k是字符串字母个数
Leetcode 128. 最长连续序列
题意理解：
给定一个未排序的整数数组
nums，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。请你设计并实现时间复杂度为O(n)的算法解决此问题。即使用nums中的元素，排序的话，能够连续的最长序列是多少呢。
这里的要求是时间复杂度O(n)
尝试使用hash的方法来解题。
解题思路：
hash解题的主要问题是：如何构造索引和值的映射。
这里：我们将最长序列的长度作为值。而index为当前元素。
（1）首先对数组进行重。set
（2） 在set中找一个序列的下界
nums[i] 且set不包含nums[i]-1
` (3) 遍历长度。length++
(4)用result记录最长的长度
哈希解题：
public int longestConsecutive(int[] nums) {
int result=0;
Set<Integer> set = new HashSet<>();
for(int i=0;i< nums.length;i++) set.add(nums[i]);
for(int num:set){
if(!set.contains(num-1)){
int length=0;
while(set.contains(num)){
length++;
num++;
}
result=Math.max(result,length);
}
}
return result;
}复杂度分析：
时间复杂度：O(n)所有元素仅遍历一遍
空间复杂度：O(n)，set的空间损耗
双指针模块
双指针：
在遍历一个数组遍历过程中定义两个指针，可以表示为：快指针和慢指针、或左指针和右指针。
双指针法（快慢指针法）在数组和链表的操作中是非常常见的，很多考察数组、链表、字符串等操作的面试题，都使用双指针法。
摘自：《代码随想录》
Leetcode 283. 移动零
题意理解：
给定一个数组
nums，编写一个函数将所有0移动到数组的末尾，同时保持非零元素的相对顺序。请注意 ，必须在不复制数组的情况下原地对数组进行操作。这道题目要求在不复制数组的情况下原地操作，使所有的0移到数组末尾。
这里采用双指针来解决这道题目
解题思路：
这里使用两个指针：慢指针i用于寻找元素0；快指针用于寻找0后的第一个非0元素
不断将非零元素和零元素进行互换，将0元素全部移至数组末尾
特别的：对于j的约束： j要小于等于nums.length,若j后续没有找到合适的非0元素，则结束，不操作。
双指针解题：
public void moveZeroes(int[] nums) {
for(int i=0;i<nums.length;i++){
if(nums[i]==0){//找到0元素时
//查找后续非0元素，j的指示
int j=i;
while(j<nums.length&&nums[j]==0) j++;
//找到后续非0元素，互换
if(j< nums.length){
int temp=nums[i];
nums[i]=nums[j];
nums[j]=temp;
}else{
//末尾无非0元素。
i=nums.length;
}
}
}
}复杂度分析：
时间复杂度：O(n) , 所有元素遍历一遍的时间复杂度
空间复杂度：O(1) ，在原数组操作，仅有temp的空间消耗，所以是O(1)
Leetcode 11. 盛最多水的容器
题意理解：
给定一个长度为
n的整数数组height。有n条垂线，第i条线的两个端点是(i, 0)和(i, height[i])。找出其中的两条线，使得它们与
x轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。
这道题目要求求容器可以存储的最大水量，储水量=h*w
其中使用双指针来i指示左边界，j指示右边界。
h=min(height[i],height[j])
w=j-i
解题思路：
选中一个左边界，一个右边界，计算S
保留尽可能高的边界，以备更多的储水量，所以，对于两个边界中较矮的边界进行移动，以期待获取一个比当前边界更大的边界。
初始化：i=0,j=nums[len-1]
计算S
当height[i]<height[j]时：i++;
否则j--,始终保持i<j
计算所有可能的S，使用maxS返回最大储水量。
双指针解题：
public int maxArea(int[] height) {
int i=0,j=height.length-1,maxS=0;
while(i<j){
int S=Math.min(height[i],height[j])*(j-i);
maxS=Math.max(maxS,S);
if(height[i]<=height[j]){
i++;
}else{
j--;
}
}
return maxS;
}复杂度分析：
时间复杂度：O(n), 所有元素遍历一遍的时间损耗
空间复杂度：O(1)，maxS的空间损耗
Leetcode 15. 三数之和
题意理解：
给你一个整数数组
nums，判断是否存在三元组[nums[i], nums[j], nums[k]]满足i != j、i != k且j != k，同时还满足nums[i] + nums[j] + nums[k] == 0。请你返回所有和为
0且不重复的三元组。注意：答案中不可以包含重复的三元组。
数组中取三个数使其和==0，每个元素每次只能去一次，可以有多少种组合。
这里求的是组合数，与顺序无关。
我们采用双指针方式来解题。
解题思路：
首先对数组进行排序。
其中我们选中一个元素nums[i]
以i+1为左边界left，len-1为右边界right， 查找符合规范的二元组，找到则加入结果集。
特别的，对于去重操作：
已知数组有序，且i确定的情况下，nums[left]不取重，left++; nums[right]不取重，right++
对于nums[i]==nums[i+1]的情况下，nums[i]已经包含了nums[i+1]的方式，所以，nums[i+1]时，continue
1.双指针解题
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> result=new ArrayList<>();
for(int i=0;i< nums.length-1;i++){
if(i>0&&nums[i]==nums[i-1]) continue;
int left=i+1;
int right= nums.length-1;
while(left<right){
if(nums[i]+nums[left]+nums[right]>0) right--;
else if (nums[i]+nums[left]+nums[right]<0) left++;
else {
//去重
result.add(Arrays.asList(nums[i],nums[left],nums[right]));
while(left<right&&nums[left+1]==nums[left]) left++;
while(left<right&&nums[right-1]==nums[right]) right--;
left++;
right--;
}
}
}
return result;
}2.复杂度分析
时间复杂度：O(n^2),遍历i的时间损耗*双指针操作时间损耗
空间复杂度：O(n), 结果集存储元素的损耗
Leetcode 42. 接雨水
题意理解：
给定
n个非负整数表示每个宽度为1的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
给定一个柱子的高度数组，求这些柱子组成的形状中，能积的水的量。
每个积水量的涉及S=w*h
其中左边界left,右边界right, 则w=right-left-1
h=max(height[left],height[right])
我们尝试使用双指针的方式解题。
解题思路：
选中一个柱子作为左边界，右边界为该柱子后第一个比它大的值，底初始化为该柱子后第一个比它小的值。
则左边界一定满足：height[i]>height[i+1]
注意：特别的：如4、2、3左边界高4时，右边没有比4高的柱子，则选择右边最高的柱子作为右边界。
1.双指针解题
public int trap(int[] height) {
int S=0;
for(int i=0;i<height.length-1;i++){
int bottom=i+1;
if(height[i]>height[bottom]){//找左边界：只有一高一低，才有可能存在储水左边界
int j=i+1;
int right=j;//右边最大的值
while(j<height.length){
//找储水有边界，有两种情况：
// 左边第一个比左边界大的柱子
// 或右边最大的柱子（右边没有比左边大的柱子）
//右边最大值
if(height[j]>=height[right]){
right=j;
}
//右边第一个比它大的值
if(height[j]>=height[i]){
right=j;
break;
}
j++;
}
//要使积水，则右边界和左边界之间最少有一个位置的空隙，保证j合法
if(right<height.length&&j-i>1){//有左右边界及底
//纵向计算该范围内的储水量
while(bottom<right){
S+=(Math.min(height[i],height[right])-height[bottom])*1;//一个单位一个单位蓄水量累加
bottom++;
}
i=right-1;
}
}
}
return S;
}2.复杂度分析
时间复杂度：O(n^2)
空间复杂度：O(1)
