【算法合集】学习算法第四天（哈希篇）

￡神魔★判官ぃ 2024-05-23 18:59 28阅读 0赞

> ✅?个人主页：[程序猿追][Link 1]
> 
> ✅?系列专栏：[算法合集][Link 2]
> 
> ✅?目前状态：创建Java学习之路（零基础到就业实战）系列，目前更新到JAVAWEB开发
> 
> ✅?作者简介：大家好，我是程序猿追，全栈领域新星创作者，算法爱好者，常在作者周榜排名前30，某不知名的 ACMer
> 
> ✅?推荐一款刷题面试找工作三不误的网站——[牛客网][Link 3]
> 
> ✅?个人名言：不积跬步无以至千里，趁年轻，使劲拼，给未来的自己一个交代！

**目录**

两数之和

题解代码

数组中出现次数超过一半的数字

题解代码

数组中只出现一次的两个数字

题解代码

缺失的第一个正整数

题解代码

三数之和

题解代码

--------------------

## 两数之和 ##

**描述**

> 给出一个整型数组 numbers 和一个目标值 target，请在数组中找出两个加起来等于目标值的数的下标，返回的下标按升序排列。
> 
> （**注：**返回的数组下标从1开始算起，保证target一定可以由数组里面2个数字相加得到）
> 
> 数据范围：2≤len(numbers)≤105，0≤numbersi≤109，0≤target≤109
> 
> **要求：**空间复杂度 O(n)，时间复杂度 O(nlogn)

> **✨示例1**
> 
> **输入：**
> 
> \[3,2,4\],6
> 
> **返回值：**
> 
> \[2,3\]
> 
> **说明：**
> 
> 因为 2+4=6 ，而 2的下标为2 ， 4的下标为3 ，又因为 下标2 < 下标3 ，所以返回\[2,3\]
> 
> **✨示例2**
> 
> **输入：**
> 
> \[20,70,110,150\],90
> 
> **返回值：**
> 
> \[1,2\]
> 
> **说明**：
> 
> 20+70=90

### 题解代码 ###

import java.util.*;
    public class Solution {
        public int[] twoSum (int[] numbers, int target) {
            int[] res = new int[0];
            //创建哈希表,两元组分别表示值、下标 fast-template
            HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>();
            //在哈希表中查找target-numbers[i]
            for(int i = 0; i < numbers.length; i++){
                int temp = target - numbers[i];
                 //若是没找到，将此信息计入哈希表
                if(!hash.containsKey(temp)){
                    hash.put(numbers[i], i);
                }
                //否则返回两个下标+1
                else
                    return new int[] {hash.get(temp) + 1, i + 1};
            }
            return res; }
    }

## 数组中出现次数超过一半的数字 ##

**描述**

> 给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
> 
> 例如输入一个长度为9的数组\[1,2,3,2,2,2,5,4,2\]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。
> 
> **数据范围：**n≤50000，数组中元素的值 0≤val≤10000
> 
> **要求**：空间复杂度：O(1)，时间复杂度 O(n)
> 
> **输入描述：**
> 
> 保证数组输入非空，且保证有解

> **✨示例1**
> 
> **输入：**
> 
> \[1,2,3,2,2,2,5,4,2\]
> 
> **返回值：**
> 
> 2
> 
> **✨示例2**
> 
> **输入：**
> 
> \[3,3,3,3,2,2,2\]
> 
> **返回值：**
> 
> 3
> 
> **✨示例3**
> 
> **输入：**
> 
> \[1\]
> 
> **返回值：**
> 
> 1

### 题解代码 ###

import java.util.*;
    public class Solution {
        public int MoreThanHalfNum_Solution(int [] array) {
             //哈希表统计每个数字出现的次数 fast-template
            HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>();
            //遍历数组
            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;}
    }

## 数组中只出现一次的两个数字 ##

**描述**

> 一个整型数组里除了两个数字只出现一次，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
> 
> 数据范围：数组长度 2≤n≤1000，数组中每个数的大小0<val≤1000000  
> 要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)

提示：输出时按非降序排列。

> **✨示例1**
> 
> **输入：**
> 
> \[1,4,1,6\]
> 
> **返回值：**
> 
> \[4,6\]
> 
> **说明：**
> 
> 返回的结果中较小的数排在前面
> 
> **✨示例2**
> 
> **输入：**
> 
> \[1,2,3,3,2,9\]
> 
> **返回值：**
> 
> \[1,9\]

### 题解代码 ###

import java.util.*;
    public class Solution {
        public int[] FindNumsAppearOnce (int[] array) {
            HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>();
            ArrayList<Integer> res = new ArrayList<Integer>();
            //遍历数组 fast-template
            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);
            //遍历数组
            for(int i = 0; i < array.length; i++)
                //找到频率为1的两个数
                if(mp.get(array[i]) == 1)
                    res.add(array[i]);
             //整理次序
            if(res.get(0) < res.get(1))
                return new int[] {res.get(0), res.get(1)};
            else
                return new int[] {res.get(1), res.get(0)};}
    }

## 缺失的第一个正整数 ##

**描述**

> 给定一个未排序的整数数组nums，请你找出其中没有出现的最小的正整数
> 
> 进阶： 空间复杂度 O(1)，时间复杂度 O(n)
> 
> **数据范围:**
> 
> \-2^31<=nums\[i\]<=2^31-1
> 
> 0<=len(nums)<=5\*105

> **✨示例1**
> 
> **输入：**
> 
> \[1,0,2\]
> 
> **返回值：**
> 
> 3
> 
> **✨示例2**
> 
> **输入：**
> 
> \[-2,3,4,1,5\]
> 
> **返回值：**
> 
> 2
> 
> **✨示例3**
> 
> **输入：**
> 
> \[4,5,6,8,9\]
> 
> **返回值：**
> 
> 1

### 题解代码 ###

import java.util.*;
    public class Solution {
        public int minNumberDisappeared (int[] nums) {
            int n = nums.length;
            HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>();
            //哈希表记录数组中出现的每个数字 fast-template
            for(int i = 0; i < n; i++)
                mp.put(nums[i], 1);
            int res = 1;
            //从1开始找到哈希表中第一个没有出现的正整数
            while(mp.containsKey(res))
                res++;
            return res; }
    }

## 三数之和 ##

**描述**

> 给出一个有n个元素的数组S，S中是否有元素a,b,c满足a+b+c=0？找出数组S中所有满足条件的三元组。
> 
> 数据范围：0≤n≤3000，数组中各个元素值满足∣val∣≤100
> 
> 空间复杂度：O(n^2)，时间复杂度 O(n^2)
> 
> **注意：**
> 
> 1.  三元组（a、b、c）中的元素可以按任意顺序排列。
> 2.  解集中不能包含重复的三元组。

> **✨示例1**
> 
> **输入：**
> 
> \[-10,0,10,20,-10,-40\]
> 
> **返回值：**
> 
> \[\[-10,-10,20\],\[-10,0,10\]\]
> 
> **✨示例2**
> 
> **输入：**
> 
> \[-2,0,1,1,2\]
> 
> **返回值：**
> 
> \[\[-2,0,2\],\[-2,1,1\]\]
> 
> **✨示例3**
> 
> **输入：**
> 
> \[0,0\]
> 
> **返回值：**
> 
> \[\]

### 题解代码 ###

import java.util.*;
    public class Solution {
        public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
            ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer>>();
            int n = num.length;
            //不够三元组 fast-template
            if(n < 3)
                return res;
            //排序
            Arrays.sort(num);
            for(int i = 0; i < n - 2; i++){
                if(i != 0 && num[i] == num[i - 1])
                    continue;
                //后续的收尾双指针
                int left = i + 1;
                int right = n - 1;
                 //设置当前数的负值为目标
                int target = -num[i];
                while(left < right){
                    //双指针指向的二值相加为目标，则可以与num[i]组成0
                    if(num[left] + num[right] == target){
                        ArrayList<Integer> temp = new ArrayList<Integer>();
                        temp.add(num[i]);
                        temp.add(num[left]);
                        temp.add(num[right]);
                        res.add(temp);
                        while(left + 1 < right && num[left] == num[left + 1])
                            //去重
                            left++;
                        while(right - 1 > left && num[right] == num[right - 1])
                            //去重
                            right--;
                        //双指针向中间收缩
                        left++;
                        right--;
                    }
                    //双指针指向的二值相加大于目标，右指针向左
                    else if(num[left] + num[right] > target)
                        right--;
                    //双指针指向的二值相加小于目标，左指针向右
                    else left++;
                }
            }
            return res;}
    }

> 算法对程序员来说及其重要，语言和开发平台不断变化，但是万变不离其宗的是那些算法和理论，依稀记得我那个玩的很好的一个学长（在大二就拿到了 offer），他告诉我想找一个好的工作，那刷题一定是必不可少的
> 
> 现在算法刷题平台还是蛮多的，给大家介绍一个我认为与大厂关联最深的平台——[牛客网][Link 3]

[Link 1]: https://blog.csdn.net/aasd23?spm=1000.2115.3001.5343
[Link 2]: https://blog.csdn.net/aasd23/category_11805404.html?spm=1001.2014.3001.5482
[Link 3]: https://www.nowcoder.com/link/pc_csdncpt_cxyz_sf