哈希（牛客）

题目来自牛客题目库 算法篇面试必刷TOP101。

BM50 两数之和(简单)

题目

题目链接

给出一个整型数组 numbers 和一个目标值 target，请在数组中找出两个加起来等于目标值的数的下标，返回的下标按升序排列。

（注：返回的数组下标从1开始算起，保证target一定可以由数组里面2个数字相加得到）

数据范围：2≤len(numbers)≤10^5^，−10≤numbers~i~≤10^9^，0≤target≤10^9^

要求：空间复杂度 O(n)，时间复杂度 O(logn)

示例：

示例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  

解法 哈希表

哈希表的下标为自然数。

• step 1：构建一个哈希表，其中key值为遍历数组过程中出现过的值，value值为其相应的下标，因为我们最终要返回的是下标。
• step 2：遍历数组每个元素，如果目标值减去该元素的结果在哈希表中存在，说明我们先前遍历的时候它出现过，根据记录的下标，就可以得到结果。
• step 3：如果相减后的结果没有在哈希表中，说明先前遍历的元素中没有它对应的另一个值，那我们将它加入哈希表，等待后续它匹配的那个值出现即可。
• step 4：需要注意最后的结果是下标值加1.

import java.util.*;

public class Solution {

    public int[] twoSum (int[] numbers, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < numbers.length; i++) {
            int temp = target - numbers[i];
            // containsKey()方法返回哈希表中是否存在目标值的布尔值
            if(!map.containsKey(temp))
                map.put(numbers[i], i); // put()方法向哈希表中添加元素
            else
                return new int[] {map.get(temp) + 1, i + 1}; // get()方法从哈希表中获取目标值的下标
        }
        int[] res = new int[0];
        return res;
    }
}

BM51 数组中出现次数超过一半的数字(简单)

题目

题目链接

给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。

数据范围：0n≤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

解法 哈希表

• 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<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;
    }
}

BM52 数组中只出现一次的两个数字(中等)

题目

一个整型数组里除了两个数字只出现一次，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

数据范围：数组长度 2≤n≤1000，数组中每个数的大小 0<val≤1000000 要求：空间复杂度 O(1)，时间复杂度 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[] nums) {
        HashMap<Integer, Integer> hash = new HashMap<>();
        for(int i = 0; i < nums.length; i++) {
            if(!hash.containsKey(nums[i]))
                hash.put(nums[i], 1);
            else
                hash.remove(nums[i]); // remove()方法从哈希表中删除元素
        }
        ArrayList<Integer> res = new ArrayList<>();
        for(int i = 0; i < nums.length; i++)
            if(hash.containsKey(nums[i]))
                res.add(nums[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)};
    }
}

BM53 缺失的第一个正整数(中等)

题目

题目链接

给定一个无重复元素的整数数组nums，请你找出其中没有出现的最小的正整数

进阶： 空间复杂度 O(1)，时间复杂度 O(n)

数据范围:

−2^31^≤nums[i]≤2^31^−1

0≤len(nums)≤5∗10^5^

示例：

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

解法1 哈希表

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

解法2 原地哈希(没看懂)

BM54 三数之和(中等)

题目

题目链接

给出一个有n个元素的数组S，S中是否有元素a,b,c满足a+b+c=0？找出数组S中所有满足条件的三元组。

数据范围：0≤n≤1000，数组中各个元素值满足∣val∣≤100

空间复杂度：O(n^2^)，时间复杂度 O(n^2^)

注意：

1. 三元组（a、b、c）中的元素必须按非降序排列。（即a≤b≤c）
2. 解集中不能包含重复的三元组。

示例：

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

解法 双指针

数组排序后遍历数组元素，在当前元素的后面找两个数，其和为当前数的相反数。注意去除重复元素。

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;
        //不够三元组
        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;
    }
}