Canvas is not supported in your browser.
首页 课程 文章
无痕注入 APC注入 线程注入 读写驱动 注入技术 句柄表 进程线程 系统调用 保护模式 内存管理 远程CALL 软件调试 驱动封装 云下发 驱动开发 FPS数据 方框透视 FPS方框 FPS自瞄 CE D3DHOOK D3D绘制 Imgui绘制 DWM
内核课程 驱动出租 学习路线 聊天室 免责声明 提问技巧

算法-代码随想录 -- 哈希表

推荐 原创

周杰伦

文章分类 其他 算法 散列表 哈希算法 leetcode 数据结构 阅读数 : 212 阅读时长 : 9分钟


【算法-代码随想录 -- 哈希表】此文章归类为：["算法","散列表","哈希算法","leetcode","数据结构"]。

文章目录

有效的字母异位词

题目链接

描述

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

示例 1: 输入: s = “anagram”, t = “nagaram” 输出: true

示例 2: 输入: s = “rat”, t = “car” 输出: false

说明: 你可以假设字符串只包含小写字母

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

题解

可以使用暴力 双层循环

也可以使用一个数组作为哈希表

class Solution {
    
public:
    bool isAnagram(string s, string t) {
    
    	int records[26]{
    0};
    	int len_s = s.size(),len_t=t.size();
    	
    	if(len_s!=len_t)return false;
    	
    	for (int i = 0; i<len_s;++i)
    		++records[s[i]-'a'];
    		
    	for (int i = 0; i < len_t; ++i)
    		--records[t[i]-'a'];
    	//record数组如果有的元素不为零0，说明字符串s和t一定是谁多了字符或者谁少了字符，return false
    	for(int i=0;i<26;++i){
    
    		if (records[i])
    			return false;
    	}
    	//如果record数组所有元素都为零0，说明字符串s和t是字母异位词，return true
    	return true;
    }
};

两个数组的交集

题目链接

描述

给定两个数组，编写一个函数来计算它们的交集。
在这里插入图片描述
输出结果中的每个元素一定是唯一的。 我们可以不考虑输出结果的顺序。

题解

class Solution {
    
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
    
    	unordered_set<int>set(nums1.begin(),nums1.end());
    	unordered_set<int>result_set;
    	for(auto n : nums2){
    
    		if(set.find(n)!=set.end())
    			result_set.insert(n);
    	}
    	return vector<int>(result_set.begin(), result_set.end());
    }
};

快乐数

题目链接

描述

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为 1，那么这个数就是快乐数。

如果 n 是快乐数就返回 True ；不是，则返回 False 。

示例：

输入：19
输出：true
解释：
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

题解

题目中说了会 无限循环，那么也就是说求和的过程中，sum会重复出现，这对解题很重要！
当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法了。
所以这道题目使用哈希法，来判断这个sum是否重复出现，如果重复了就是return false， 否则一直找到sum为1为止。

class Solution {
    
public:
	int getSum(int n){
    
		int sum{
    0};
		while(n){
    
			int tmp = n%10;
			sum+=tmp*tmp;
			n/=10;
		}
		return sum;
	}
    bool isHappy(int n) {
    
    	unordered_set<int>result;
    	while(true){
    
    		n = getSum(n);
    		if(n==1)return true;
    		//没找到n
    		if(result.find(n)==result.end()){
    
    			result.insert(n);
    		}else
    			return false;
    	}
    }
};

两数之和

题目链接

描述

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

题解

显然可以暴力 但不是优解

什么时候使用map：当查询一个元素是否出现 或者 一个元素是否在一个集合之中，优先使用哈希表

class Solution {
    
public:
    vector<int> twoSum(vector<int>& nums, int target) {
    
        unordered_map<int,int>result;
        int len = nums.size();
        for (int i = 0; i < len;++i){
    
        	//存在
        	auto cur = result.find(target-nums[i]);
        	if( cur != result.end())
        		return {
    i,cur->second};
        	else{
    
        		result.insert(make_pair(nums[i],i));
        	}
        }
        return {
    };
    }
};

四数相加II

题目链接

描述

给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。

为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -2^28 到 2^28 - 1 之间，最终结果不会超过 2^31 - 1 。

例如:

输入:

A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]
输出:

2

解释:

两个元组如下:

(0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
(1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

题解

时间复杂度：O(n)

四个数组

先将前两个遍历，求和，作为key存入哈希表，如果有重复的key将value+1

然后遍历后两个，求和，其和的相反数如果存在哈希表中，那么最终结果+对应的value

class Solution {
    
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
    
    	unordered_map<int,int>map;
    	int count{
    0};
    	for(int n1:nums1)
    		for(int n2:nums2)
    			map[n1+n2]++;
    	for(int n3:nums3){
    
    		for(int n4:nums4){
    
    			int target = 0 - (n3+n4);
    			if(map.find(target)!=map.end())
    				count+=map[target];
    		}
    	}
    	return count;
    }
};

赎金信

题目链接

描述

给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。

(题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)

注意：

你可以假设两个字符串均只含有小写字母。

canConstruct(“a”, “b”) -> false
canConstruct(“aa”, “ab”) -> false
canConstruct(“aa”, “aab”) -> true

题解：暴力

class Solution {
    
public:
    bool canConstruct(string ransomNote, string magazine) {
    
        for (int i = 0; i < magazine.length(); i++) {
    
            for (int j = 0; j < ransomNote.length(); j++) {
    
                // 在ransomNote中找到和magazine相同的字符
                if (magazine[i] == ransomNote[j]) {
    
                    ransomNote.erase(ransomNote.begin() + j); // ransomNote删除这个字符
                    break;
                }
            }
        }
        // 如果ransomNote为空，则说明magazine的字符可以组成ransomNote
        if (ransomNote.length() == 0) {
    
            return true;
        }
        return false;
    }
};

题解：哈希表

数组作为哈希表 都是小写 总共26个 有限单元可数组

class Solution {
    
public:
    bool canConstruct(string ransomNote, string magazine) {
    
    	int flag[26]{
    0};
    	for(auto c:magazine)
    		flag[c-'a']++;
    	for(auto c:ransomNote)
    		flag[c-'a']--;
    	for(int i:flag){
    
    		if(i<0)
    			return false;
    	}
    	return true;
    }
};

三数之和

题目链接

描述

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

注意： 答案中不可以包含重复的三元组。

题解：哈希表（不适合）

class Solution {
    
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
    
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        // 找出a + b + c = 0
        // a = nums[i], b = nums[j], c = -(a + b)
        for (int i = 0; i < nums.size(); i++) {
    
            // 排序之后如果第一个元素已经大于零，那么不可能凑成三元组
            if (nums[i] > 0) {
    
                break;
            }
            if (i > 0 && nums[i] == nums[i - 1]) {
     //三元组元素a去重
                continue;
            }
            unordered_set<int> set;
            for (int j = i + 1; j < nums.size(); j++) {
    
                if (j > i + 2
                        && nums[j] == nums[j-1]
                        && nums[j-1] == nums[j-2]) {
     // 三元组元素b去重
                    continue;
                }
                int c = 0 - (nums[i] + nums[j]);
                if (set.find(c) != set.end()) {
    
                    result.push_back({
    nums[i], nums[j], c});
                    set.erase(c);// 三元组元素c去重
                } else {
    
                    set.insert(nums[j]);
                }
            }
        }
        return result;
    }
};

题解：双指针

首先将数组排序，然后有一层for循环，i从下标0的地方开始，同时定一个下标left 定义在i+1的位置上，定义下标right 在数组结尾的位置上。

依然还是在数组中找到 abc 使得a + b +c =0，我们这里相当于 a = nums[i]，b = nums[left]，c = nums[right]。

接下来如何移动left 和right呢， 如果nums[i] + nums[left] + nums[right] > 0 就说明 此时三数之和大了，因为数组是排序后了，所以right下标就应该向左移动，这样才能让三数之和小一些。

如果 nums[i] + nums[left] + nums[right] < 0 说明 此时 三数之和小了，left 就向右移动，才能让三数之和大一些，直到left与right相遇为止

如果 nums[i] + nums[left] + nums[right] = 0 了 说明符合结果 此时由于进入for循环的第一步就对a进行了去重，那么只有b和c重复的情况 所以对b和c进行去重

class Solution {
    
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
    
        sort(nums.begin(),nums.end());
        vector<vector<int>>result;
        size_t len = nums.size();
        for(int i = 0;i<len;++i){
    
        	if(nums[i]>0)break;
        	if(i>0&&nums[i]==nums[i-1])continue;
        	int left = i+1,right = len-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.push_back(vector<int>{
    nums[i],nums[left],nums[right]});
        			while(left<right&&nums[right]==nums[right-1])--right;
        			while(left<right&&nums[left]==nums[left+1])++left;

        			++left;
        			--right;
        		}
        	}
        }
        return result;
    }
};

四数之和

题目链接

描述

题意：给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：

答案中不可以包含重复的四元组。

示例： 给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。 满足要求的四元组集合为： [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]

题解：双指针

class Solution {
    
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
    
    	sort(nums.begin(), nums.end());
    	size_t len = nums.size();
    	vector<vector<int>>result;
    	for(int k=0;k<len;++k){
    
    		// 剪枝处理
    		if(nums[k]>target&&nums[k]>=0)break;
    		 // 对nums[k]去重
    		if(k>0&&nums[k]==nums[k-1])continue;

    		for(int i=k+1;i<len;++i){
    
    			int first_result = nums[k]+nums[i];
    			// 2级剪枝处理
    			if(first_result>target&&first_result>=0)break;
    			// 对nums[i]去重
    			if(i>k+1&&nums[i]==nums[i-1])continue;

    			int left = i+1,right = len-1;
    			while(left<right){
    
					//int会溢出
    				if((long)first_result+nums[left]+nums[right]>target)
    					--right;
    				else if((long)first_result+nums[left]+nums[right]<target)
    					++left;
    				else{
    
    					result.push_back(vector<int>{
    nums[k],nums[i],nums[left],nums[right]});
    					while (right > left && nums[right] == nums[right - 1]) right--;
                        while (right > left && nums[left] == nums[left + 1]) left++;
                        --right;
                        ++left;
    				}
    			}
    	}

    }
       return result;
	}
};


更多【算法-代码随想录 -- 哈希表】相关视频教程：www.yxfzedu.com




相关文章推荐

记录自己的技术轨迹
文章规则：
1)：文章标题请尽量与文章内容相符
2)：严禁色情、血腥、暴力
3)：严禁发布任何形式的广告贴
4)：严禁发表关于中国的政治类话题
5)：严格遵守中国互联网法律法规
6)：有侵权,疑问可发邮件至service@yxfzedu.com
近期原创 更多
友情链接
内核结构 FAQ
免责声明
课程目录
Windows内核
游戏逆向(FPS)
技术交流QQ群
342478842 215039827 137189196
314055665 159620936
微信公众号
www.yxfzedu.com是一个分享游戏安全,游戏外挂与反外挂,游戏驱动保护的视频网站！
接各种驱动定制如：游戏读写驱动，软件内存保护，防止调试等功能定制。
出租读写驱动，调试驱动，无痕注入支持各种游戏。
邮箱：service@yxfzedu.com
QQ：851920120
特别说明：不接游戏数据分析，外挂编写，登陆协议等类似业务。