各位小伙伴们大家好，今天继续跟着小曾哥开启刷题之旅，此文章专题为哈希表，希望能够与各位小伙伴们共勉进步！
文章目录
💎1、两数之和
题目描述：给出一个整型数组 numbers 和一个目标值 target，请在数组中找出两个加起来等于目标值的数的下标，返回的下标按升序排列。
输入：[3,2,4],6
返回值：[2,3]
说明：因为 2+4=6 ，而 2的下标为2 ， 4的下标为3 ，又因为 下标2 < 下标3 ，所以返回[2,3]
🏆直接遍历(暴力解法)
import java.util.*;
public class Solution {
/**
*
* @param numbers int整型一维数组
* @param target int整型
* @return int整型一维数组
*/
public int[] twoSum (int[] numbers, int target) {
// write code here
int n = numbers.length;
int[] res = {-1, -1};
//遍历数组
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
//判断相加值是否为target
if (numbers[i] + numbers[j] == target) {
res[0] = i+1;
res[1] = j+1;
//返回值
return res;
}
}
}
return res;
}
}
这种方法在牛客上进行编程，是不通过的，运行超时，其实条条大路通罗马。
🏆利用hash表
注意到方法一的时间复杂度较高的原因是寻找 target - x 的时间复杂度过高。因此，我们需要一种更优秀的方法，能够快速寻找数组中是否存在目标元素。如果存在，我们需要找出它的索引。
使用哈希表，可以将寻找 target - x 的时间复杂度降低到从 O(N)O(N) 降低到 O(1)O(1)。
这样我们创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; ++i) {
if (hashtable.containsKey(target - nums[i])) {
return new int[]{hashtable.get(target - nums[i]), i};
}
hashtable.put(nums[i], i);
}
return new int[0];
}
}
import java.util.*;
public class Solution {
/**
*
* @param numbers int整型一维数组
* @param target int整型
* @return int整型一维数组
*/
public int[] twoSum (int[] numbers, int target) {
// write code here
int[] res = new int[0];
// 创建hashmap表，分别表示值和下标
HashMap<Integer, Integer> hash = new HashMap<>();
// 在hash表中进行查找
for(int i =0; i< numbers.length;i++){
int temp = target - numbers[i];
// 如果没有找到
if(!hash.containsKey(temp)){
hash.put(numbers[i],i);
}
// 否则,返回下标
else
return new int[] {hash.get(temp)+1,i+1};
}
return res;
}
}
💎2、数组中出现次数超过一半的数字
题目描述：给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。
🏆Hash法
根据题目意思，显然可以先遍历一遍数组，在map中存每个元素出现的次数，然后再遍历一次数组，找出众数。
具体步骤：
step 1：构建一个哈希表，统计数组元素各自出现了多少次，即key值为数组元素，value值为其出现次数。
step 2：遍历数组，每遇到一个元素就把哈希表中相应key值的value值加1，用来统计出现次数。
step 3：本来可以统计完了之后统一遍历哈希表找到频次大于数组长度一半的key值，但是根据我们上面加粗的点，只要它出现超过了一半，不管后面还有没有，必定就是这个元素了，因此每次统计后，我们都可以检查value值是否大于数组长度的一半，如果大于则找到了。
import java.util.*;
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
// 哈希表统计每个数字出现的次数
HashMap<Integer, Integer> mp = new HashMap<>();
// 遍历数组
for(int i=0;i<array.length;i++){
if(!mp.containsKey(array[i]))
mp.put(array[i],1);
else{
mp.put(array[i],mp.get(array[i])+1);
}
if(mp.get(array[i]) > array.length / 2)
return array[i];
}
return 0;
}
}
时间复杂度：O(n)
空间复杂度：O(n)
🏆排序法
可以先将数组排序，然后可能的众数肯定在数组中间，然后判断一下。
import java.util.*;
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
Arrays.sort(array);
return array[(array.length)/2];
}
}
时间复杂度：因为使用了Arrays.sort()方法，实现的是快速排序，所以时间复杂度为O(nlogn)，相比哈希法要消耗更多的时间。
空间复杂度：若是题目明确要求不能改变原来的数组，则需要创建一个新的与原来的数组一样的数组，空间复杂度O(n)，若是没有要求，则可以直接在原来的数组上修改，空间复杂度O(1)。
💎3、数组中只出现一次的两个数字
题目描述：一个整型数组里除了两个数字只出现一次，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
输入：[1,4,1,6]
返回值：[4,6]
说明：返回的结果中较小的数排在前面
🏆哈希表
与题目2很类似，处理方式有些许不同，都属于同一类的题目。
当题目中出现数组，次数，这个时候就可以考虑用哈希表来存储对应元素和
具体步骤：
step 1：遍历数组，用哈希表统计每个数字出现的频率。
step 2：然后再遍历一次数组，对比哈希表，找到出现频率为1的两个数字。
step 3：最后整理次序输出。
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param array int整型一维数组
* @return int整型一维数组
*/
public int[] FindNumsAppearOnce (int[] array) {
// 用hash表
HashMap<Integer,Integer> hash = new HashMap<>();
// 创建数组进行保存结果
ArrayList<Integer> res = new ArrayList<>();
// 遍历数组
for(int i=0;i< array.length;i++){
if(!hash.containsKey(array[i]))
hash.put(array[i],1);
else{
hash.put(array[i],hash.get(array[i])+1);
}
}
//遍历hash表
for(int i=0;i<array.length;i++){
if(hash.get(array[i]) == 1)
res.add(array[i]);
}
// 整理次序
if(res.get(0) > res.get(1))
return new int[]{res.get(1), res.get(0)};
else{
return new int[]{res.get(0),res.get(1)};
}
}
}
对于这种快速查询某个元素是否出现过的问题，还是可以使用哈希表。
💎4、缺失的第一个正整数
题目描述：给定一个无重复元素的整数数组nums，请你找出其中没有出现的最小的正整数
进阶： 空间复杂度 O(1)，时间复杂度 O(n)
输入：[-2,3,4,1,5]
返回值：2
🏆哈希表
思路解析：n个长度的数组，没有重复，则如果数组填满了1～n，那么缺失n+1，如果数组填不满1～n，那么缺失的就是1～n中的数字。对于这种快速查询某个元素是否出现过的问题，还是可以使用哈希表。
具体步骤：
step 1：构建一个哈希表，用于记录数组中出现的数字。
step 2：从1开始，遍历到n，查询哈希表中是否有这个数字，如果没有，说明它就是数组缺失的第一个正整数，即找到。
step 3：如果遍历到最后都在哈希表中出现过了，那缺失的就是n+1.
public class Solution {
public int minNumberDisappeared (int[] nums) {
// write code here
int n = nums.length;
HashMap<Integer, Integer> hash = new HashMap<>();
// hash记录数组中出现的数字
for(int i=0; i<n;i++){
hash.put(nums[i],1);
}
int res = 1;
// 从1开始查找第一个没有出现的元素
while(hash.containsKey(res)){
res++;
}
return res;
}
}
💎5、三数之和
题目描述：给出一个有n个元素的数组S，S中是否有元素a,b,c满足a+b+c=0？找出数组S中所有满足条件的三元组。
注意：
三元组（a、b、c）中的元素可以按任意顺序排列。
解集中不能包含重复的三元组。
输入：[-10,0,10,20,-10,-40]
返回值：[[-10,-10,20],[-10,0,10]]
输入：[-2,0,1,1,2]
返回值：[[-2,0,2],[-2,1,1]]
🏆排序+双指针
import java.util.*;
public class Solution {
public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
ArrayList<ArrayList<Integer>> Lists = new ArrayList<>();
// 排序
Arrays.sort(num);
// 双指针
int len = num.length;
for(int i=0;i<len;i++){
//
if(num[i] > 0) return Lists;
if(i>0 && num[i] == num[i-1]) continue;
int cur = num[i];
int left = i+1 ,right = len-1;
while(left<right){
int tmp = cur + num[left]+ num[right];
if(tmp == 0){
ArrayList<Integer> list = new ArrayList<>();
list.add(cur);
list.add(num[left]);
list.add(num[right]);
Lists.add(list);
// 开始找下一个解
while(left < right && num[left+1] == num[left]) ++left;
while(left < right && num[right -1] == num[right]) --right;
++left;
--right;
}
else if(tmp < 0){
++left;
}
else{
--right;
}
}
}
return Lists;
}
}