代码随想录：哈希表
哈希表是根据关键码的值直接访问数据的数据结构，可以根据一个key直接访问数据
哈希表一般用来快速判断一个元素是否出现在集合中
查询一个学生是否在学校名单上枚举的话时间复杂度为O(n)，用哈希表时间复杂度为O(1)
将学生的名字映射到哈希表上就涉及到哈希函数，哈希函数是通过hashCode通过特定编码方式将其他数据转化为不同数值
为了保证映射出来的索引数值都落在哈希表上，对数值进行一个取模操作保证所有数据都可以映射到哈希表
哈希碰撞：两个数据映射到哈希表同一索引位置，此现象即为哈希碰撞，解决办法一般有两种，拉链法和线性探测法
拉链法，在某一索引位置发生冲突的元素全部存储到链表中，要适当选择哈希表的大小防止因数组空值浪费内存或因链表太长在查找上浪费时间
线性探测法（*要求tableSize>dataSize)依靠哈希表中的空位解决问题，冲突位置已经存放了一个信息就向下找一个空位存放新的信息
常见的三种哈希结构：数组，set（集合），map（映射）（c#中对应Dictionary）
当我们需要快速判断一个元素是否出现在集合中时考虑使用哈希法，哈希法牺牲空间换取时间
力扣242：有效的字母异位词
public class Solution {
public bool IsAnagram(string s, string t) {
int[] rec=new int[26];
//要求只有小写字母因此建立长度为26的数组
for(int i=0;i<s.Length;i++){
rec[s[i]-'a']++;
//把每次s中出现的字母对应的元素+1
}
for(int j=0;j<t.Length;j++){
rec[t[j]-'a']--;
//每次t中出现的字母对应元素-1
}
for(int k=0;k<26;k++){
if(rec[k]!=0){
return false;
//若有元素不是0说明s和t字符不一样，返回false
}
}
return true;
}
}
力扣349：两个数组的交集
public class Solution {
public int[] Intersection(int[] nums1, int[] nums2) {
HashSet<int> hs1 = new HashSet<int>(nums1);
HashSet<int> r=new HashSet<int>();
foreach(int n in nums2){
if(hs1.Contains(n)){
r.Add(n);
//将其中一个数组放进集合里，遍历另一个数组寻找集合中有无重复数字，有就添加到保存结果的集合里
}
}
return r.ToArray();
//结果集合转化成数组
}
}
力扣1：两数之和
public class Solution {
public int[] TwoSum(int[] nums, int target) {
Dictionary<int,int> map=new Dictionary<int, int>();
int[] rsl = new int[2];
for (int i = 0; i < nums.Length; i++)
{
int a = target - nums[i];
if (map.ContainsKey(a))
{
rsl[0] = i;
rsl[1] = map[a];
//一边遍历一边填表，在表格中找符合条件的数
}
if(!map.TryAdd(nums[i],i)){
map[a]=i;
//根据TryAdd的返回值判断有无重复数字决定是否更新map中的value位置
}
}
return rsl;
}
}
力扣454：四数之和II
public class Solution {
public int FourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
Dictionary<int,int > map= new Dictionary<int, int>();
foreach (int a in nums1)
{
foreach (int b in nums2)
{
map.TryAdd(a+b,0);
//建立的map中初始化以后为空，第一次需要手动填入key和value
map[a + b]++;
//统计a+b结果出现的次数作为value
}
}
int count = 0;
foreach (int c in nums3)
{
foreach (int d in nums4)
{
if (map.ContainsKey(0-c-d))
{
count += map[0 - c - d];
//统计0-c-d的结果在map中出现的次数再与count自身相加即为所求结果
}
}
}
return count;
}
}
力扣15：三数之和
public class Solution {
public IList<IList<int>> ThreeSum(int[] nums)
{
IList<IList<int>> result = new List<IList<int>>();
Array.Sort(nums);
for (int i = 0; i < nums.Length; i++)
{
if (nums[i]>0)
{
break;
//若排序后第一个数字大于0则停止寻找
}
if (i>0&&nums[i]==nums[i-1])
{
continue;
//若i重复则进行下一次循环
}
HashSet<int> set = new HashSet<int>();
//靠每次循环重新定义set来清空set
for (int j = i+1; j < nums.Length; j++)
{
if (j>i+2&& nums[j]== nums[j-1]&& nums[j]==nums[j-2])
{
continue;
//若j重复则进行下一次循环
}
int c = 0 - nums[i] - nums[j];
if (set.Contains(c))
{
IList<int> cur = new List<int>();
cur.Insert(0,nums[i]);
cur.Insert(1,nums[j]);
cur.Insert(2,c);
result.Add(cur);
set.Remove(c);
//排除重复的c
}
else
{
set.Add(nums[j]);
//若没找到就将set更新
}
}
}
return result;
}
}
/*本题比起哈希表更适合用双指针法，遍历一次数组第0到nums.Length-2位，对每个数用left和right两个指针指向它的下一位和最后一位，并根据三数相加结果决定left和right指针向中间移动，有结果则记录下来，实现代码如下*/
public class Solution {
public IList<IList<int>> ThreeSum(int[] nums)
{
Array.Sort(nums);
IList<IList<int>> rsl = new List<IList<int>>();
int i = 0, j = 0, k = 0;
for ( i = 0; i < nums.Length-2; i++)
{
if (i>0&&nums[i]==nums[i-1])
{
continue;
//去重复
}
j = i + 1;
k = nums.Length - 1;
while (j<k)
{
if (nums[k]+nums[j]+nums[i]<0)
{
j += 1;
//left指针移动
while (j<k&&nums[j]==nums[j-1])
{
j += 1;
//去重复
}
}
else if (nums[k]+nums[j]+nums[i]>0)
{
k -= 1;
//right指针移动
while (j<k&&nums[k]==nums[k+1])
{
k -= 1;
//去重复
}
}
else
{
List<int> temp=new List<int>(3);
temp.Add(nums[i]);
temp.Add(nums[j]);
temp.Add(nums[k]);
rsl.Add(temp);
j += 1;
//找到结果后未遍历结束要继续遍历
while (j<k&&nums[j]==nums[j-1])
{
j += 1;
}
k -= 1;
while (j<k&&nums[k]==nums[k+1])
{
k -= 1;
//找到结果后也要去重复
}
}
}
}
return rsl;
}
}
力扣18：四数之和
//解法与上一道题相同，只是要循环外多套一次for循环，然后再用双指针法找到符合条件的数
public class Solution {
public IList<IList<int>> FourSum(int[] nums,int target)
{
IList<IList<int>> result = new List<IList<int>>();
Array.Sort(nums);
for (int i = 0; i < nums.Length; i++)
{
if (i>0&& nums[i]==nums[i-1])
{
continue;
}
for (int j = i+1; j < nums.Length; j++)
{
if (j>i+1&& nums[j]==nums[j-1])
{
continue;
}
int left = j + 1;
int right = nums.Length - 1;
while (left<right)
{
long s = (long)nums[i] + (long)nums[j] + (long)nums[right] + (long)nums[left];
//这里由于-10^9<= nums[i] <= 10^9导致进行加法计算时可能出现数据溢出的情况，因此转换成long型进行计算
if (s>target)
{
right--;
}
else if (s<target)
{
left++;
}
else
{
List<int> temp=new List<int>(4);
temp.Add(nums[i]);
temp.Add(nums[j]);
temp.Add(nums[left]);
temp.Add(nums[right]);
result.Add(temp);
while (right>left&& nums[right]==nums[right-1])
{
right--;
}
while (right>left&& nums[left]==nums[left+1])
{
left++;
}
right--;
left++;
}
}
}
}
return result;
}
}
