350. 两个数组的交集 II
题目分析
给定两个数组,编写一个函数来计算它们的交集。
示例 1:
输入:nums1 = [1,2,2,1], nums2 = [2,2] 输出:[2,2]
示例 2:
输入:nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出:[4,9]
思路分析
方法一:hash表
因为不去重,不考虑顺序,而且考虑到了效率我们可以采用unordered_map类型的hash表
把nums1中的元素放到unordered_map nums1_map中,然后遍历nums2中的每个元素num.
如果num在numsMap的值>0,则说明可以放到交集里面…如果等于0,则从numsMap中移除.
方法二:双指针
思路与LeetCode384相似,不再赘述
参考代码
方法一:hash表
//方法一:使用unordered_map解决. 原因:因为同一个数存在多个,可以使用键值对来进行存储,结果不要求顺序. //时间复杂度O(N) 空间复杂度O(N) vector<int> intersect(vector<int>& nums1, vector<int>& nums2) { vector<int> result; unordered_map<int,int> nums1_map; for(int i = 0; i < nums1.size(); i++) { //初始化nums1_map nums1_map[nums1[i]]++; } //遍历nums2,将重复的元素加入结果集. for(int i = 0; i < nums2.size(); i++) { if(nums1_map.find(nums2[i])!=nums1_map.end()) { nums1_map[nums2[i]]--; result.push_back(nums2[i]);//元素放入结果集 if(nums1_map[nums2[i]]==0) { //如果已经减到了0,则移除 nums1_map.erase(nums2[i]); } } } return result; }
时间复杂度:O ( n )
空间复杂度:O ( n )
方法二:双指针
//方法二: 双指针 vector<int> intersect(vector<int>& nums1, vector<int>& nums2) { int i = 0,j = 0; vector<int> result; //排序 sort(nums1.begin(),nums1.end()); sort(nums2.begin(),nums2.end()); while(i<nums1.size()&&j<nums2.size()){ if(nums1[i]==nums2[j]){//如果想等 result.push_back(nums1[i]);//加入结果集 i++;//同时移动 j++; }else if(nums1[i]<nums2[j]){//值小的指针往前移动 i++; }else if(nums1[i]>nums2[j]){ j++; } } return result; }
202. 快乐数
题目描述
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」定义为:
对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。
如果 可以变为 1,那么这个数就是快乐数。
如果 n 是快乐数就返回 true ;不是,则返回 false 。
示例 1:
输入:n = 19 输出:true
解释:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
示例 2:
输入:n = 2 输出:false
思路分析:
注意: 题目中的可能会无限循环,也就是说在求和的过程中,sum会重复出现.
所以我们就可以对该数进行快乐的判断,每次如果不是1,说明该数目前不是快乐数.
同时要在set中寻找该数是否曾经出现过,如果出现过则说明出现了循环则一定不是快乐数.
如果还没有出现则持续进行判断…
参考代码
#include<bits/stdc++.h> using namespace std; int getSum(int x){//将数替换成数字的平方和 int sum = 0; while(x){ sum+=(x%10)*(x%10); x /= 10; } return sum; } //由于只需要存这个元素在集合中是否存在,而且不需要重复,所以我们使用unordered_set unordered_set<int> set; bool isHappy(int n) { int res = getSum(n); while(res!=1){ if(set.find(res)!=set.end()){ return false; }else{ set.insert(res); } res = getSum(res); } return true; }
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]
思路分析
方法一:暴力法
双层for循环走起来 ~ ~ ~
方法二:hash表(unordered_map)
因为每次不仅要存数,还要存储其下标,所以我们使用map,因为不需要有序和重复性,我们可以选择:unordered_map M
用i遍历所有的元素,在M中查找是否存在元素 target - nums[i],如果存在则说明找到了,返回当前元素和这个元素的下标.
如果没有找到则将当前元素和下标插入到M中.
参考代码
方法一:暴力法
//方法一:暴力法 vector<int> twoSum(vector<int>& nums, int target) { for(int i = 0;i < nums.size();i++) { for(int j = i+1;j < nums.size();j++){ return {i,j}; } } return {}; }
时间复杂度:O ( n 2 )
空间复杂度:O ( 1 )
方法二:hash表
vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int,int> M;//存放元素以及对应的下标 for(int i = 0; i < nums.size(); i++) { unordered_map<int,int>::iterator iter = M.find(target-nums[i]);//查找其和为target的另外 一个元素是否存在 if(iter!=M.end()) { return {i,iter->second}; } M.insert(pair<int,int>(nums[i],i));//如果没有,则将当前元素插进来. } return {};//写这个只是为了编译通过,实际运行根本不会走这一步.. }
时间复杂度:O ( n )
空间复杂度:O ( n )
15. 三数之和
题目描述
给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组。
注意:答案中不可以包含重复的三元组。
示例 1:
输入:nums = [-1,0,1,2,-1,-4] 输出:[[-1,-1,2],[-1,0,1]]
示例 2:
输入:nums = [] 输出:[]
示例 3:
输入:nums = [0] 输出:[]
思路分析
排序 + 双指针
(1). 特判,对于数组长度 n,如果数组长度小于 3,返回 []。
(2). 对数组进行排序。
(3).遍历排序后数组:
若 nums[i]>0:因为已经排序好,所以后面不可能有三个数加和等于 0,直接返回结果。
对nums[i] (代表的就是a)进行去重.
令左指针 L=i+1,右指针 R=n-1,当 L
(4) 当 nums[i]+nums[L]+nums[R]==0执行循环,判断左界和右界是否和下一位置重复,去除重复解。并同时将 L,R 移到下一位置,寻找新的解
(5).若和大于 0,说明nums[R] 太大,R左移
(6).若和小于 0,说明 nums[L] 太小,L右移
复杂度分析
参考代码
#include<bits/stdc++.h> using namespace std; vector<vector<int>> threeSum(vector<int>& nums) { int L,R,sum; vector<vector<int>> res; if(nums.size()<3) { return {} ; } //进行排序 sort(nums.begin(),nums.end()) ; //如果第一个元素就>0,那么后面的元素一定 > 0 if(nums[0]>0) { return {}; } //遍历元素+双指针 for(int i = 0; i<nums.size(); i++) { if(nums[i]>0) { return res; } if(i>0&&nums[i]==nums[i-1]) { //进行去重 continue; } L = i+1; R = nums.size()-1; while(L < R) {//采用双指针法 枚举所有的三元对情况 sum = nums[i]+nums[L]+nums[R]; if(!sum) { res.push_back({nums[i],nums[L],nums[R]}); //进行去重 while(L + 1<R && nums[L]==nums[L+1]) { L++; } while(R-1 > L && nums[R]==nums[R-1]) { R--; } L++; R--; } else if(sum > 0) { R--; } else if(sum < 0) { L++; } } } return res; }
18. 四数之和
题目描述
给你一个由 n 个整数组成的数组 nums ,和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] (若两个四元组元素一一对应,则认为两个四元组重复):
0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。
示例 1:
输入:nums = [1,0,-1,0,-2,2], target = 0 输出:[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2:
输入:nums = [2,2,2,2,2], target = 8 输出:[[2,2,2,2]]
思路分析
和三数之和解决思路基本一致.三数之和只是 i 固定,左右指针进行变化.
四数之和是i,j固定,然后左右指针进行变化,当左右指针变化一轮后,j进行后移一位.j移动完一轮后,i后移一位…
参考代码
#include<bits/stdc++.h> using namespace std; //这个题思路和上一个题非常相似 vector<vector<int>> fourSum(vector<int>& nums, int target) { vector<vector<int>> res; int len = nums.size(); long long i,j,k,l, sum; if(nums.size()<4) { return {}; } //进行排序 sort(nums.begin(),nums.end()) ; // if(nums[0]>target){//这里不能根据第一个数来判断最终结果,因为target可能是正数,负数,0 // return {}; // } //定义两个变量+双指针 枚举所有的情况 for(i = 0; i <= len-4; i++) { //去重i元素 if(i > 0 && nums[i]==nums[i-1]) {//去重 continue; } for( j = i+1; j <= len - 3; j++) { //去重 if(j > i+1 && nums[j] == nums[j-1]) { continue; } //定义双指针 int k = j+1; int l = len - 1; while(k < l) { sum = 0; sum += nums[i]; sum += nums[j]; sum += nums[k]; sum += nums[l]; if(sum==target) { res.push_back({nums[i],nums[j],nums[k],nums[l]}); //进行去重 while(k+1 < l &&nums[k] == nums[k+1] ) { k++; } while(l-1>k&& nums[l]==nums[l-1]) { l--; } //指针移动 k++; l--; } else if(sum < target) { k++; } else if(sum > target) { l--; } } } } return res; }
454. 四数相加 II
题目描述
给你四个整数数组 nums1、nums2、nums3 和 nums4 ,数组长度都是 n ,请你计算有多少个元组 (i, j, k, l) 能满足:
0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
示例 1:
输入:nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2] 输出:2
解释:
两个元组如下:
(0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
(1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0
示例 2:
输入:nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0] 输出:1
思路分析
由于a,b,c,d是在四个数组里面的,所以可以使用四个循环. 为了降低时间复杂度,我们可以将a、b分为一组,c、d分为一组. 利用map类型的hash表统计其出现的次数.
首先定义 一个unordered_map ,key放a和b两数之和,value 放a和b两数之和出现的次数。
遍历大A和大B数组,统计两个数组元素之和,和出现的次数,放到map中。
在遍历大C和大D数组,如果 0-(c+d) 在map中出现过的话,统计其出现的次数.
最后返回统计值 cnt
参考代码
#include<bits/stdc++.h> using namespace std; int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) { unordered_map<int,int> M; int cnt = 0; for(int A : nums1){ for(int B : nums2){ M[A+B]++; } } for(int C: nums3){ for(int D: nums4){ auto iter = M.find(0-A-B); if(M.find(0-A-B)!=M.end()) { cnt+=iter->second; } } } return cnt; }
总结
OK,今天关于hash表算法整理就到这里的,希望本篇文章能够帮助到大家,同时也希望大家看后能学有所获!!!
好了,我们下期见~