数据结构与算法刷题之【哈希表】篇

文章目录

前言
哈希表基础知识
基本概念
最简单哈希：字符哈希
Hash表的实现（手写Map）
HashMap 基本使用
剑指offer
剑指 Offer 03. 数组中重复的数字【简单】
剑指 Offer 50. 第一个只出现一次的字符【简单】
剑指 Offer 53 - I. 在排序数组中查找数字【简单】
剑指 Offer 57. 和为s的两个数字【简单】
剑指 Offer 61. 扑克牌中的顺子【简单】
剑指 Offer 56 - I. 数组中数字出现的次数【中等，等同牛客第3题】
剑指 Offer 56 - II. 数组中数字出现的次数 II【中等】
剑指 Offer 35. 复杂链表的复制【中等】
剑指 Offer II 004. 只出现一次的数字【中等】
剑指 Offer II 070. 排序数组中只出现一次的数字【中等】
牛客
两数之和【简单】
数组中出现次数超过一半的数字是【简单】
数组中只出现一次的两个数字【中等，重点】
缺失的第一个正整数【中等】
leetcode
202. 快乐数【简单】
1. 两数之和【简单】
349. 两个数组的交集【简单】
169. 多数元素【简单】
448. 找到所有数组中消失的数字【简单】
242. 有效的字母异位词【简单】
383. 赎金信【简单】
三数之和【中等】
18. 四数之和【中等】
454. 四数相加 II【中等】
1224. 最大相等频率【困难】

前言

除了去年11月份以及今年近几月的算法刷题之外，只有在当时20年蓝桥杯准备的时候才刷过一些题，在当时就有接触到一些动归、递归回溯、贪心等等，不过那会也还是一知半解，做的题目也特别少，因为考虑到之后面试有算法题以及数据结构算法对于一个程序员十分重要，我也开始了刷题之路。

我目前的学习数据结构与算法及刷题路径：

1、学习数据结构的原理以及一些常见算法。

2、代码随想录：跟着这个github算法刷题项目进行分类刷，在刷题前可以学习一下对应类别的知识点，而且这里面每道题都讲的很详细。

3、牛客网高频面试101题：牛客网—面试必刷101题，在刷的过程中可以在leetcode同步刷一下。

4、接下来就是力扣上的专栏《剑指offer II》、《程序员面试金典（第 6 版）》...有对应的精选题单来对着刷即可。

5、大部分的高频面试、算法题刷完后，就可以指定力扣分类专栏进行一下刷题了。

刚开始刷的时候真的是很痛苦的，想到去年一道题可能就需要好几小时，真的就很难受的，不过熬过来一切都会好起来，随着题量的增多，很多题目你看到就会知道使用什么数据结构或者算法来去求解，并且思考对应的时间空间复杂度，并寻求最优解，我们一起加油！

我的刷题历程

截止2022.8.18：

1、牛客网101题(其中1题是平台案例有问题)：

2、剑指offerII：

力扣总记录数：

加油加油！

哈希表基础知识

代码随想录—哈希表理论基础

遇到需要判断一个元素是否出现过的场景也应该第一时间想到哈希法

基本概念

哈希表（Hash table，也叫散列表），是根据关键字（key）直接进行访问的数据结构，它通过把关键值映射到表中一个位置（数组下标）来直接访问，以加快查找关键值的速度。这个映射函数叫做哈希（散列）函数，存放记录的数组叫做哈希（散列）表。

给定表（M），存在函数f（key），对任意的关键值key，代入函数后若能得到包含该关键字的表中地址，称表M为哈希表，函数f（key）为哈希函数。

最终会计算key的哈希值接着计算出数组索引位置。

最简单哈希：字符哈希

最简单的哈希：字符哈希，因为字符的个数有限，那么即可使用字符的ascii来作为数组的下标。

/**
 * @ClassName CharHash
 * @Author ChangLu
 * @Date 4/2/2022 10:07 AM
 * @Description 字符哈希：使用字符的ascii来作为哈希的下标
 */
public class CharHash {

    //题：对给定字符串中的字符进行统计
    public static void main(String[] args) {
        String str = "asdfsafdsdddfdsf";
        countAppearChat(str);
    }

    /**
     * 将字符串中的每个字符的ascii码作为统计数组的下标。由于字符数量有限可以直接使用其作为索引下标统计
     * @param str 
     */
    public static void countAppearChat(String str){
        int[] chs = new int[128];
        for (int i = 0; i < str.length(); i++) {
            chs[str.charAt(i)]++;
        }
        for (int i = 0; i < 128; i++) {
            if (chs[i] > 0){
                System.out.println(String.format("字符%c出现了%d次",(char)i,chs[i]));
            }
        }
    }

}

Hash表的实现（手写Map）

问题引入1：任意元素的映射（若是我们想让任何元素来进行映射，具备数组索引的效果，那么需要解决的是如何将key这种非num类型的转为对应的索引下标）

解决：利用哈希函数

思路：将关键值（大整数、字符串、浮点数等）转化为整数再对表长取余，从而关键字值被转换为哈希表的表长范围内的整数。

问题引入2：不同整数或字符串，由于哈希函数的选择，映射到同一个下标，发生冲突。（那么假设大数key的计算得到的哈希与原本计算得到的出现了重复，那么这种情况如何解决？）

解决：拉链法解决冲突

思路：①将所有哈希函数结果相同的结点连接在同一个单链表中。【数组+链表】②将对应连接的链表转为树来进行存储【数组+红黑树，JDK中1.8以上hashMap实现】

下面是①方式实现的存储、插入、搜索思路及代码：

//存储
存储：若选定的哈希表长度为m，则可将哈希表定义为一个长度为m的指针数组t[0…m-1]，指针数组中的每个指针指向哈希函数结果相同的单链表。【数组中存储的node结点可以是链表中的结点带有next指针，这种能够方便在出现哈希冲突时采用头插法或尾插法方式来插入到对应结点的前后】
//插入
插入：将value对应的结点key以头插法的方式插入到以t[hash_key]为头指针的单链表中
//搜索
搜索：遍历以t[hash_key]为头指针的单链表，查找链表各个结点的值域是否为value
    
//手写简易版的HashMap
/**
 * @ClassName DiyHashMap
 * @Author ChangLu
 * @Date 4/2/2022 10:34 AM
 * @Description 手写数组+链表：最最简单的一个HashMap实现
 */
class Node{
    private Object key;
    private Object value;
    private Node next;

    public Node(Object key,Object value) {
        this.key = key;
        this.value = value;
    }

    public Node(Object key,Object value, Node next) {
        this.key = key;
        this.value = value;
        this.next = next;
    }

    public Object getValue() {
        return value;
    }

    public void setValue(Object value) {
        this.value = value;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    public Object getKey() {
        return key;
    }

    public void setKey(Object key) {
        this.key = key;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        Node node = (Node) o;

        if (key != null ? !key.equals(node.key) : node.key != null) return false;
        if (value != null ? !value.equals(node.value) : node.value != null) return false;
        return next != null ? next.equals(node.next) : node.next == null;
    }

    @Override
    public int hashCode() {
        int result = key != null ? key.hashCode() : 0;
        result = 31 * result + (value != null ? value.hashCode() : 0);
        result = 31 * result + (next != null ? next.hashCode() : 0);
        return result;
    }

    @Override
    public String toString() {
        return "Node{" +
                "key=" + key +
                ", value=" + value +
                ", next=" + next +
                '}';
    }
}

class MyMap{
    Node[] nodes;

    //构建Map的容量
    public MyMap(int capacity){
        if (capacity < 16) {
            nodes = new Node[capacity];
        }else {
            //计算出capacity最高幂
            nodes = new Node[Integer.highestOneBit(capacity)];
        }
    }

    //插入
    public void put(Object key,Object value){
        //1、计算key的hash值
        int hashKey =  key.hashCode() & (nodes.length - 1);
        //2、获取对应下标Node结点，看是否存在
        Node node = nodes[hashKey];
        //若是不存在直接插入
        if (node == null){
            nodes[hashKey] = new Node(key,value);
            return;
        }
        //若是存在，遍历Node结点(若是有结点，直接覆盖)
        Node cur = node;
        while (cur != null) {
            //判断key是否相同
            if (key.equals(cur.getKey())) {
                cur.setValue(value);
                return;
            }
            cur = cur.getNext();
        }
        //若是没有结点，采用头插法
        nodes[hashKey] = new Node(key,value,node);
    }

    //获取
    public Object get(Object key){
        //1、获取到对应的node结点
        int hashKey =  key.hashCode() & (nodes.length - 1);
        //2、遍历node来获取对应的值
        Node node = nodes[hashKey];
        Node cur = node;
        while (cur != null){
            //判断对应的node结点的key是否相同，若是相同那么直接返回
            if (cur.getKey().equals(key)){
                return cur.getValue();
            }
            cur = cur.getNext();
        }
        return null;
    }

}

public class DiyHashMap {

    public static void main(String[] args) {
        final MyMap myMap = new MyMap(20);
        myMap.put("changlu","123");
        myMap.put("changlu","456");
        System.out.println(myMap.get("changlu"));
        System.out.println(myMap.get("liner"));
    }

}

HashMap 基本使用

1、基本使用（1）插入键值对数据

public V put(K key, V value)

（2）根据键值获取键值对值数据

public V get(Object key)

（3）获取Map中键值对的个数

public int size()

（4）判断Map集合中是否包含键为key的键值对

public boolean containsKey(Object key)

（5）判断Map集合中是否包含值为value的键值对

boolean containsValue(Object value)

（6）判断Map集合中是否没有任何键值对

public boolean isEmpty()

（7）清空Map集合中所有的键值对

public void clear()

（8）根据键值删除Map中键值对

public V remove(Object key)

2、遍历（1）将Map中所有的键装到Set集合中返回

//public Set keySet(); Set set=map. keySet()

（2）返回集合中所有的value的值的集合

// public Collection values(); Collection c=map.values()

（3）将每个键值对封装到一个个Entry对象中,再把所有Entry的对象封装到Set集合中返回

// public Set<Map.Entry<K,V>> entrtSet(); Set<Map.Entry<K,V>> entrys=map.entrySet()

HashMap<String,Integer> map =new HashMap<>();
map.put("a", 1);
map.put("b", 2);
map.put("c", 3);
map.put("d", 4);

//key封装成一个set集合即可进行遍历
final Iterator<String> iterator = map.keySet().iterator();

//将key、value封装到一个entry中，接着将多个entry放置到一个set里，最后使用迭代器方式来进行迭代遍历
final Iterator<Map.Entry<String, Integer>> mapIterator = map.entrySet().iterator();
while (mapIterator.hasNext()) {
    final Map.Entry<String, Integer> next = mapIterator.next();
    System.out.println(String.format("key:%s,value:%d",next.getKey(),next.getValue()));
}

剑指offer

剑指 Offer 03. 数组中重复的数字【简单】

参考文章：剑指 Offer 03. 数组中重复的数字（哈希表 / 原地交换，清晰图解）

题目链接：剑指 Offer 03. 数组中重复的数字

题目内容：在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

解法：

1、暴力：nxn来进行比较。

复杂度分析：

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

2、哈希表：

时间复杂度：O(n)
空间复杂度：O(n)

class Solution {
    public int findRepeatNumber(int[] nums) {
        //采用哈希
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                return nums[i];
            }else {
                map.put(nums[i], 1);
            }
        }
        return -1;
    }
}

3、原地交换法（最优解）：

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

核心条件：题目给出的核心条件值为[0, n - 1]，值与索引对应。

class Solution {
    //原地解法
    //核心条件：nums中的数字值范围为[0, n - 1]
    public int findRepeatNumber(int[] nums) {
        int i = 0;
        while (i != nums.length) {
            int num = nums[i];
            if (num == i) {  //若是索引为本身不作操作
                i++;
            }else if (num == nums[num]) { //若是本身值与对应索引位置的值相同，说明重复
                return num;
            }else {
                //若是当前值与索引值不相等的话，那么就进行交换值（其实就是将自己这个索引值换到目标索引位置上，那么之后若是有出现相等的值找索引就能够快速找到了）
                //对于交换后i无需++，示例：3,4,2,1,1,0，一定要当前索引位置再进行检查一遍
                nums[i] = nums[num];
                nums[num] = num;  
            }
        }
        return -1;
    }
}

剑指 Offer 50. 第一个只出现一次的字符【简单】

题目链接：剑指 Offer 50. 第一个只出现一次的字符

题目内容：在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。

思路：

1、字典表，双层遍历【简单】

复杂度分析：

时间复杂度：O(n)
空间复杂度：O(n)

class Solution {

    //第一个只出现一次的  s中只包含小写字母
    public char firstUniqChar(String s) {
        if (s == null || s.length() == 0) {
            return ' ';
        }
        //26个字母
        int[] target = new int[26];
        for (int i = 0; i < s.length(); i++) {
            target[s.charAt(i) - 'a']++;
        }
        for (int i = 0; i < s.length(); i++) {
            if (target[s.charAt(i) - 'a'] == 1) {
                return s.charAt(i);
            }
        }
        return ' ';
    }
    
}

剑指 Offer 53 - I. 在排序数组中查找数字【简单】

题目链接：剑指 Offer 53 - I. 在排序数组中查找数字 I

题目内容：统计一个数字在排序数组中出现的次数。

思路：

1、二分+搜索。

复杂度分析：

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

class Solution {
    public int search(int[] nums, int target) {
        //1、定位数字的索引位置
        //123 45   12 34
        int left = 0, right = nums.length - 1;
        int mid = -1;
        boolean flag = false;
        while (left <= right) {
            mid = (left + right) / 2;
            if (nums[mid] == target) {
                flag = true;
                break;
            }else if (nums[mid] < target) {
                left = mid + 1;
            }else {
                right = mid - 1;
            }
        }
        int res = 0;
        if (flag) {
            //2、左右去进行搜索
            res++;
            int x = mid - 1;
            int y = mid + 1;
            while (x >= 0 && nums[x] == target) {
                x--;
                res++;
            }
            while (y < nums.length && nums[y] == target) {
                y++;
                res++;
            }
        }
        return res;
    }
}

剑指 Offer 57. 和为s的两个数字【简单】

题目链接：剑指 Offer 57. 和为s的两个数字

题目内容：输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。

思路：看到递增首先就应该想到二分

1、哈希表

复杂度分析：时间O(n)、空间O(n)

class Solution {

    //递增、两数之和
    //滑动窗口
    public int[] twoSum(int[] nums, int target) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (set.contains(target - nums[i])) {
                return new int[]{nums[i], target - nums[i]};
            }
            set.add(nums[i]);
        }
        return new int[]{};
    }
}

2、双指针【最优】

复杂度分析：时间(n)、空间O(1)

class Solution {

    //递增、两数之和
    //双指针写法
    public int[] twoSum(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        //定位到右边指针<=target的位置
        while (r >= 0 && nums[r] > target) {
            r--;
        }
        int[] res = new int[2];
        //进行双指针变换
        while (l < r) {
            int num = nums[l] + nums[r];
            if (num == target) {
                res[0] = nums[l];
                res[1] = nums[r];
                break;
            }else if (num < target) {
                l++;
            }else {
                r--;
            }
        }
        return res;
    }

}

剑指 Offer 61. 扑克牌中的顺子【简单】

题目链接：剑指 Offer 61. 扑克牌中的顺子

题目内容：从若干副扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。

思路：小大王为0可表示任意数，这题解题思路就在于max-min是否小于5，5就是牌的数量，还有就是过程中有没有出现过相同的牌。

1、set+遍历【推荐】

复杂度分析：时间O(n)、空间O(n)。由于最大n就是14，那么我们可以将其都看作是O(1)

class Solution {

    //聚焦于最大值-最小值（中间判断是否有重复的数）
    //set判重+遍历
    public boolean isStraight(int[] nums) {
        int[] bucket = new int[14];
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        //桶14个，来进行索引计数判断是否有重复的
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                bucket[nums[i]]++;
                if (bucket[nums[i]] > 1) {
                    return false;
                }
                min = Math.min(min, nums[i]);
                max = Math.max(max, nums[i]);
            }
        }
        return max - min < 5;
    }

}

2、排序+计数遍历

复杂度分析：时间O(n+logn*n)、空间O(1)

class Solution {

    //聚焦于最大值-最小值（中间判断是否有重复的数）
    //排序+计数
    public boolean isStraight(int[] nums) {
       Arrays.sort(nums);
       int joker = 0;
       for (int i = 0; i < nums.length; i++) {
           if (nums[i] == 0) {
                joker++;
           }else {
                //处理中间相同的情况
                if (i > 0 && nums[i] == nums[i - 1]) {
                    return false;
                }
           }
       }
       return nums[4] - nums[joker] < 5;
    }

}

剑指 Offer 56 - I. 数组中数字出现的次数【中等，等同牛客第3题】

题目链接：剑指 Offer 56 - I. 数组中数字出现的次数

题目内容：一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

思路：

1、哈希

2、位运算

复杂度分析：时间复杂度O(n)、空间复杂度O(1)

class Solution {
    //位运算
    public int[] singleNumbers(int[] nums) {
        int num = nums[0];
        for (int i = 1; i < nums.length; i++) {
            num ^= nums[i];
        }
        int k = 1;
        //找到k & num > 0的情况
        while ((k & num) == 0) {
            k = k << 1;
        }
        int num1 = 0;
        int num2 = 0;
        //二次遍历，拆分成两个进行异或操作
        for (int i = 0; i < nums.length; i++) {
            if ((k & nums[i]) > 0) {
                num1 ^= nums[i];
            }else {
                num2 ^= nums[i];
            }
        }
        return new int[]{num1, num2};
    }
}

剑指 Offer 56 - II. 数组中数字出现的次数 II【中等】

学习资料：视频：LeetCode刷题力扣题解 | 剑指Offer56 - II. 数组中数字出现的次数 II | 画图算法思路讲解及C++代码实现、博客-数组中数字出现的次数Ⅱ

题目链接：剑指 Offer 56 - II. 数组中数字出现的次数 II

题目内容：在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

思路：

1、哈希表

2、位运算。既然出现了三次，我们就将每个数字的所有位进行相加，每一位最终%3，然后计算这个二进制数最终得到的值就是只出现一次的数字。

复杂度分析：时间复杂度O(n)，空间复杂度O(1)

class Solution {
    public int singleNumber(int[] nums) {
        //int 32位
        int[] counts = new int[32];
        int k = 1;//进位
        //对nums数组中的每个元素的每一位来进行相加
        for (int num: nums) {
            for (int i = 0; i < 32; i++) {
                counts[i] += num & k;
                num = num >> 1;
            }
        }
        //对所有统计的数字来进行计算
        int res = 0;
        for (int i = 0; i < 32; i++) {
            res = res + (counts[i] % 3) * k;
            k = k << 1;
        }
        return res;
    }
}

剑指 Offer 35. 复杂链表的复制【中等】

学习视频：LeetCode刷题力扣｜剑指Offer 35. 复杂链表的复制（题解思路分析及Python3代码实现）介绍了原地法

题目链接：剑指 Offer 35. 复杂链表的复制

题目内容：请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

思路：

1、哈希表：

复杂度分析：时间复杂度O(n)，实际上是2n，空间复杂度O(n)

class Solution {
    //本题的本质是：深拷贝
    //困难点：若是仅仅走一层遍历的话，对应的next、random指向的结点都不是新的结点
    public Node copyRandomList(Node head) {
        //使用map实现
        Map<Node, Node> map = new HashMap<>();
        //第一次遍历：将所有的结点都拷贝了一份
        for (Node cur = head; cur != null; cur = cur.next) {
            map.put(cur, new Node(cur.val));
        }
        //第二次遍历：将所有的空白结点的next、random来指向map中对应的next、random，实际上就是我们的一个新节点
        for (Node cur = head; cur != null; cur = cur.next) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
        }
        return map.get(head);
    }
}

2、原地修改【推荐，让空间复杂度优化为O(1)】

复杂度分析：时间复杂度O(n)，实际上是3n；空间复杂度O(1)

class Solution {
    //本题的本质是：深拷贝
    //困难点：若是仅仅走一层遍历的话，对应的next、random指向的结点都不是新的结点
    public Node copyRandomList(Node head) {
        if (head == null) {
            return head;
        }
        //原地修改：1->2->3
        //第一遍遍历：每个结点指向相同值的新节点
        //1->1'->2->2'->3->3'->null
        for (Node cur = head; cur != null; cur = cur.next.next) {  //注意是两个next
            Node newNode = new Node(cur.val);
            newNode.next = cur.next;
            cur.next = newNode;
        }
        //第二遍遍历：为所有的新节点random来进行赋值
        for (Node cur = head; cur != null; cur = cur.next.next) {
            if (cur.random != null) {
                cur.next.random = cur.random.next;//同样这里next指向的是random相同值的新节点
            }
        }
        //第三遍遍历：分离旧新节点（原始的、新的都要进行分离）
        //1->2->3->null
        //1'->2'->3'->null
        Node newNode = head.next;
        for (Node node = head, temp = null; node != null && node.next !=null;) {
            temp = node.next;
            node.next = temp.next;
            node = temp;
        }
        return newNode;
    }
}

剑指 Offer II 004. 只出现一次的数字【中等】

题目链接：剑指 Offer II 004. 只出现一次的数字，类似题与该目录里的牛客3类似。

题目内容：给你一个整数数组 nums ，除某个元素仅出现一次外，其余每个元素都恰出现 **三次。**请你找出并返回那个只出现了一次的元素。

思路1：哈希表。

复杂度分析：

时间复杂度：O(n)
空间复杂度：O(n)

class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num: nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        for (Map.Entry<Integer, Integer> entry: map.entrySet()) {
            if (entry.getValue() == 1) {
                return entry.getKey();
            }
        }
        return -1;
    }
}

思路2：位运算

...待做

剑指 Offer II 070. 排序数组中只出现一次的数字【中等】

教程：[LeetCode 136]. 只出现一次的数字[位运算技巧系列]

题目链接：剑指 Offer II 070. 排序数组中只出现一次的数字

题目内容：给定一个只包含整数的有序数组 nums ，每个元素都会出现两次，唯有一个数只会出现一次，请找出这个唯一的数字。

思路1：进行异或运算

异或表达式：

num ^ 0 = num
num ^ num = 0
num ^ (num1 ^ num1) = num
(num ^ num1) ^  num1 = num

复杂度分析：

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

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int ans = 0;
        for (int num: nums) {
            ans ^= num; 
        }
        return ans;
    }
}

牛客

两数之和【简单】

题目链接：两数之和

题目内容：给出一个整型数组 numbers 和一个目标值 target，请在数组中找出两个加起来等于目标值的数的下标，返回的下标按升序排列。（注：返回的数组下标从1开始算起，保证target一定可以由数组里面2个数字相加得到）

思路：通过使用一个map来作缓存，key为值，value为index。

复杂度分析：

时间复杂度：O(n)
空间复杂度：O(n)

import java.util.*;

public class Solution {
    /**
     * 
     * @param numbers int整型一维数组 
     * @param target int整型 
     * @return int整型一维数组
     */
    public int[] twoSum (int[] numbers, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0;i < numbers.length; i++) {
            int val = numbers[i];
            if (map.containsKey(target - val)) {
                return new int[]{map.get(target - val) + 1, i + 1};
            }
            map.put(val, i);
        }
        return new int[2];
    }
}

数组中出现次数超过一半的数字是【简单】

题目链接：数组中出现次数超过一半的数字

题目内容：给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。

思路1：使用一个map来存储值与次数，如key为值，value为出现数量。

复杂度分析：

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

import java.util.*;
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        //定义一个map，key存放int，value存放出现的次数
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < array.length; i++) {
            if (!map.containsKey(array[i])) {
                map.put(array[i], 1);
            }else {
                map.put(array[i], map.get(array[i]) + 1);
            }
            if (map.get(array[i]) > array.length/2) {
                return array[i];
            }
        }
        return -1;
    }
}

数组中只出现一次的两个数字【中等，重点】

题目链接：数组中只出现一次的两个数字

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

题目信息梳理：

1个长度为n的数字，除了两个数字只出现1次，其余数字都出现2次
要找到这两次只出现一次的数字，并且升序返回

思路1：采用哈希表。①遍历一遍所有数字，将其添加到哈希表中，哈希表key为num，value为计数。②遍历一遍数字，来取出value为1的所有数字。③最后来进行升序返回。

复杂度分析：

时间复杂度：O(n)
空间复杂度：O(n)

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型一维数组 
     * @return int整型一维数组
     */
    public int[] FindNumsAppearOnce (int[] array) {
        //哈希表
        Map<Integer, Integer> map = new HashMap<>();
        for (int number: array) {
            if (map.containsKey(number)) {
                map.put(number, map.get(number) + 1);
            }else {
                map.put(number, 1);
            }
        }
        int[] res = new int[2];
        int num = 0;
        //遍历一遍map集合
        for (int number: array) {
            if (map.get(number) == 1) {
                res[num++] = number;
            }
        }
        if (res[0] > res[1]) {
            return new int[]{res[1], res[0]};
        }
        return res;
    }
}

思路2：位运算【进阶】。

位运算基础：题解学习

a ^ a = 0
a ^ (b ^ b) = a
(a ^ b) ^ b = a

本道题我入手思路是先通过看代码题解(牛客网配套101题解)然后反推学习的。
步骤思路：①初始res=0然后异或所有num值，得到一个k。②然后找到这个k为1的二进制情况(k<<1推)。②接着再次遍历一遍所有数，遍历过程中去判断&值时的结果为0、1情况，最终用两个变量来记录两个数字。
案例：
①3 ^ 4 = 111
3 011
4 100
  111  求得k为001，你可以找到规律就是011 & 001 = 1 > 0、100 & 001 = 0

此时 3 ^ 4 ^ 4 ^ 6 = 111 ^ 010 = 101，本质实际上就是3 ^ 6 = 011 ^ 110 = 101，由于两个数是进行异或操作，那么某位相等的时候就是0，不相等就是1，那么找到这个不相等的位置，101中第1个或第三个位置都可，找到位置有什么用？由于位置上是不同值才能够得到1，那么一旦我们能够找到该位置就能够将其进行分组（必定能够找到，因为两个值是不相等的）。
k=1开始，当101 & 1时（循环），结果为1，那么k的最终值为1

那么使用k这个值来去&两个值看看，必定一个是0或者1，由于其他都是成对的，a ^ a = 0,我们无需关心数量了

复杂度分析：

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

class Solution {
    //位运算
    public int[] singleNumbers(int[] nums) {
        int num = nums[0];
        for (int i = 1; i < nums.length; i++) {
            num ^= nums[i];
        }
        int k = 1;
        //找到k & num > 0的情况
        while ((k & num) == 0) {
            k = k << 1;
        }
        int num1 = 0;
        int num2 = 0;
        //二次遍历，拆分成两个进行异或操作
        for (int i = 0; i < nums.length; i++) {
            if ((k & nums[i]) > 0) {
                num1 ^= nums[i];
            }else {
                num2 ^= nums[i];
            }
        }
        return new int[]{num1, num2};
    }
}

缺失的第一个正整数【中等】

题目链接：缺失的第一个正整数

题目内容：给定一个未排序的整数数组nums，请你找出其中没有出现的最小的正整数

思路1：利用哈希表。key为值，value为1，首先遍历一遍存储到哈希表中，由于题目说找到缺失的第一个正整数，那么只需要设置一个res值初始为1，然后不断对其进行自增然后判断是否在map中存在即可找到第一个正整数。

复杂度分析：

时间复杂度：O(n)，2n，第一次是遍历n个数字，第二次是遍历最大的整数值。
空间复杂度：O(n)，存储n个哈希值。

class Solution {
    public int firstMissingPositive(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0;i < nums.length;i++) {
            map.put(nums[i], 1);
        }
        int res = 1;
        while (map.containsKey(res)) {
            res++;
        }
        return res;
    }
}

思路2：原地哈希法。①首先遍历第一遍，将所有负数取值为n+1。②遍历第二遍，将索引为|nums[i] - 1|数组索引设置为负数。③遍历第三遍，若是找到第一个为正数的，其索引也就是i+1即为第一个整数，否则即为n+1。

复杂度分析：

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

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        //第一次遍历，将所有得负数修改为length + 1
        for (int i = 0; i < n; i++) {
            if (nums[i] <= 0) {
                nums[i] = n + 1;
            }
        }
        //将索引为（对应值<n得值）设置为负数，那么最终再遍历一次时非负数得索引即为第一个正数
        for (int i = 0; i < n; i++) {
            if (Math.abs(nums[i]) <= n) {
                nums[Math.abs(nums[i]) - 1] = -1 * Math.abs(nums[Math.abs(nums[i]) - 1]);
            }
        }
        //最后遍历即可得到第一个正数
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        return n + 1;
    }
}

leetcode

202. 快乐数【简单】

学习：leetcode题解、代码随想录—第202题. 快乐数

题目链接：202. 快乐数

题目内容：

编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为：
对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
如果这个过程 结果为 1，那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

思路：

1、哈希表

思路：如何判断该数会是无限循环呢？只要我们判断新生成的数是否为之前重复的，一旦是重复的就表示其是会无限循环的。出现重复问题一般使用哈希表来进行解决。

public boolean isHappy(int n) {
    //核心是是否出现重复的数
    Set<Integer> set = new HashSet<>();
    //n表示结果：n!=1以及当前容器不存在该值作为循环条件
    while(n!=1 && !set.contains(n)){
        set.add(n);//添加到容器
        n = getNewNum(n);//获取到新生成的数
    }
    //此时n要么为1，要么为在容器中出现重复的值
    return n == 1;
}

//例如：n=123 => 1*1+2*2+3*3=14
public int getNewNum(int n){
    int sum = 0;
    while(n != 0){
        sum += (n%10)*(n%10);
        n = n/10;
    }
    return sum;
}

1. 两数之和【简单】

学习：leetcode题解、代码随想录—两数之和

题目链接：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]

思路：

1、暴力求解

思路：两层遍历循环来进行匹配两数之和。

复杂度分析：时间复杂度O(n^2^)

public int[] twoSum(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i+1; j < nums.length; j++) {
            if(nums[i] + nums[j] == target){
                return new int[]{i,j};
            }
        }
    }
    return new int[]{};
}

2、map构建哈希表

思路：利用HashMap来进行存储，key为遍历值，value为下标。每遍历一个元素值v时，直接计算target-v的值也就是待求的另一部分值，使用map来进行key索引看是否存在，一旦存在就表示匹配到了直接返回，不存在当前遍历值作为key，索引为value进行存储。

复杂度分析：O(n)

public int[] twoSum(int[] nums, int target) {
    int[] res = new int[2];
    if (nums == null || nums.length < 2) {
        return res;
    }
    Map<Integer, Integer> map = new HashMap<>(nums.length / 2 + 1);
    for (int i = 0; i < nums.length; i++) {
        //nums[i] + ? = target，这里直接使用map来进行匹配是否之前有某个数
        int temp = target-nums[i];
        //一旦匹配，直接赋值进行返回
        if(map.containsKey(temp)){
            res[0] = i;
            res[1] = map.get(temp);
        }
        map.put(nums[i],i);
    }
    return res;
}

3、map+双指针

思路：其实与NO2核心思想是一致的，再此基础上使用了两个指针分别指向最左边与最右边，在使用map存储时，一次遍历相当于前后两个位置同时进行，能够大幅度提升效率。

复杂度分析：O(n)

public int[] twoSum(int[] nums, int target) {
    Map<Integer,Integer> map = new HashMap<>();
    int left = 0;
    int right = nums.length-1;
    for(;left<=right;left++,right--){
        if(map.containsKey(target-nums[left])){
            return new int[]{left,map.get(target-nums[left])};
        }
        map.put(nums[left],left);
        if(map.containsKey(target-nums[right]) && left!=right){  //避免中间相等的出现存储两次情况
            return new int[]{right,map.get(target-nums[right])};
        }
        map.put(nums[right],right);
    }
    return new int[2];
}

349. 两个数组的交集【简单】

学习：leetcode题解、代码随想录—349. 两个数组的交集

题目链接：349. 两个数组的交集

题目内容：

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是唯一的。我们可以 不考虑输出结果的顺序 。

思路：

1、set去重

思路：该题是从数组大小来看题目并没有限制，我们就不能够使用例如"有效字母异位词"方式定义数组来进行解决了，此时我们可以借助Java给我们提供的Set集合来进行解决，首先将第一组元素存储至set1中达到去重效果，接着对第二组数组进行遍历，判断每个元素是否在set1中存在，若是存在则说明该元素是两组数据的交集。

public int[] intersection(int[] nums1, int[] nums2) {
    if(nums1 == null || nums2 == null || nums1.length == 0 || nums1.length == 0){
        return new int[]{0};
    }
    Set<Integer> set1 = new HashSet<>(nums1.length);
    Set<Integer> set2 = new HashSet<>(nums2.length);

    //将某个数组中的元素进行去重存储到集合1中
    for (int i : nums1) {
        set1.add(i);
    }

    //在对下一组元素进行遍历时使用set1来进行判断是否存在该元素，若是存在存储至set2中，表示为交集元素
    for (int i : nums2) {
        if(set1.contains(i)){
            set2.add(i);
        }
    }

    //转为整型数组
    int[] distinctArr = new int[set2.size()];
    int i = 0;
    for (Integer num : set2) {
        distinctArr[i++] = num;
    }
    return distinctArr;
}

169. 多数元素【简单】

学习：leetcode题解

题目链接：169. 多数元素

题目内容：

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

速记：

①哈希表，使用哈希表来记录对应数以及对应出现的次数，最终判断对应次数是否>n/2即可。
②先进行排序，之后直接返回n/2下标的值。
③Boyer-Moore 投票算法，核心只有两个变量，一个是记录众数，另一个是投票的数量，来源于生活，真的十分的妙！

思路：

1、哈希表

思路：使用哈希表来记录对应数以及出现的次数，紧接着来进行获取到数量>n/2的指定数。

复杂度分析：时间复杂度O(n)，空间复杂度O(n)

public int majorityElement(int[] nums) {
    Map<Integer, Integer> map = new HashMap(nums.length / 2);
    //使用哈希表来进行存储对应值的数量
    for (int i = 0; i < nums.length; i++) {
        map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
    }
    //遍历哈希表来获取多数
    for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
        if (entry.getValue() > nums.length / 2) {
            return entry.getKey();
        }
    }
    return -1;
}

2、排序法

思路：先对数组进行排序，之后直接取出位置为nums.length/2的值。

复杂度分析：时间复杂度O(nlogn)，空间复杂度O(logn)，这两者都是语言自带的排序算法

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        //无论多数的那个值是大还是小，由于其数量为>n/2，那么nums[nums.length/2]绝对能够取到该值了
        return nums[nums.length/2];
    }
}

3、Boyer-Moore 投票算法

思路：仅仅使用两个变量来进行记录，将投票思路融合到这里。题目给出一组数据中肯定有一个众数，其数量>n/2，此时一个变量来记录众数，另一个变量来记录其投票数，中间的逻辑直接见注释即可。最终一定是投票数多的人获胜并且最终直接返回该众数即可！

复杂度分析：时间复杂度O(n)，空间复杂度O(1)

public int majorityElement(int[] nums) {
    int count = 1;//记录当前选举众数的次数
    int modeNum = nums[0];
    for (int i = 1; i < nums.length; i++) {
        //若是投票人数=0,直接换人，并且加上一票
        if (count == 0){
            modeNum = nums[i];
            count++;
            continue;
        }
        //此时投票人数>0，若是当前投票的数与众数不符合就-1票，否则加一票
        count = nums[i] != modeNum ? count - 1: count + 1;
    }
    return modeNum;
}

448. 找到所有数组中消失的数字【简单】

学习：leetcode题解

题目链接：448. 找到所有数组中消失的数字

题目内容：给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。

速记：

①创建长度为n的数组，为1表示该数字存在，否则不存在。实际遍历两次即可统计出对应不存在的数字。
②遍历原数组中的元素值，取得该数字-1的值，也就是等会来作为索引的下标，给该索引的值+n来作为该索引数字存在的标记(>n)，之后重新遍历一遍，一旦有某个值<=n，则表示该索引数字+1并没有存在过，即可将空间复杂度优化为O(1)。

思路：

1、哈希表

思路：创建一个长度为n的数组，中间存0表示该数字不存在，存1则表示该数字出现过。之后遍历一遍即可求得结果。

复杂度分析：时间复杂度O(n)，空间复杂度O(n)

public List<Integer> findDisappearedNumbers(int[] nums) {
    //使用一个数组来进行记录nums中存在的数字
    int[] numArr = new int[nums.length];
    for (int num : nums) {
        numArr[num - 1] = 1;
    }
    //遍历numArr，若是为0则表示不在数组出现的元素
    List<Integer> numList = new ArrayList<>();
    for (int i = 0; i < numArr.length; i++) {
        if (numArr[i] == 0) {
            numList.add(i + 1);
        }
    }
    return numList;
}

2、原地数组替换

思路：遍历原数组中的元素值，取得该数字-1的值，也就是等会来作为索引的下标，给该索引的值+n来作为该索引数字存在的标记(>n)，之后重新遍历一遍，一旦有某个值<=n，则表示该索引数字+1并没有存在过，即可将空间复杂度优化为O(1)。

复杂度分析：时间复杂度O(n)，空间复杂度O(1)

public List<Integer> findDisappearedNumbers(int[] nums) {
    int n = nums.length;
    int x;
    for (int num : nums) {
        x = (num - 1) % n;
        nums[x] += n;
    }
    //重新遍历一遍，若是有数字<n则表示该位置(即数字)没有在原数组汇总出现过
    List<Integer> numList = new ArrayList<>();
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] <= n) {
            numList.add(i + 1);
        }
    }
    return numList;
}

242. 有效的字母异位词【简单】

学习：leetcode题解、代码随想录—242.有效的字母异位词

题目链接：242. 有效的字母异位词

题目内容：

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

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

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

思路：

1、暴力法

public boolean isAnagram(String s, String t) {
    //字符串长度不相等、为0情况直接返回
    if(s == null || t == null || s.length() != t.length() || s.length() == 0){
        return false;
    }
    for (int i = 0; i < s.length(); i++) {
        int sNum = 0;
        char sChar = s.charAt(i);
        //s字符串获取当前字符的相同个数
        for (int j = 0; j < s.length(); j++) {
            if(sChar == s.charAt(j)){
                sNum++;
            }
        }
        //t字符串统计sChar的个数
        int tNum = 0;
        for (int j = 0; j < t.length(); j++) {
            if(sChar == t.charAt(j)){
                tNum++;
            }
        }
        if(tNum !=sNum){
            return false;
        }
    }
    return true;
}

2、哈希发

思路：根据提示s 和 t 仅包含小写字母，所以我们可以直接定义一个大小为26的int数组默认索引值都为0，对应下标0-25存放'a'-'z'的重复次数，之后遍历s、t来进行统计，最终可根据数组中的值是否相等或为0来确定是否为有效的字母异位词。

代码：下面是进行修改了三次，思路都是一致的

//首次看思路自己写代码
public boolean isAnagram(String s, String t) {
    if(s == null || t == null || s.length()!=t.length() || s.length() == 0){
        return false;
    }
    //设置两个数组来进行分别记录对应的字符串字符的数量
    int[] sArr = new int[26];
    int[] tArr = new int[26];
    //遍历一遍s
    for (int i = 0; i < s.length(); i++) {
        sArr[s.charAt(i)-'a']++;
        tArr[t.charAt(i)-'a']++;
    }

    for (int i = 0; i < 26; i++) {
        if(sArr[i] != tArr[i]){
            return false;
        }
    }
    return true;
}

//优化一：两个数组=>一个数组
public boolean isAnagram(String s, String t) {
    if(s == null || t == null || s.length()!=t.length() || s.length() == 0){
        return false;
    }
    //使用一个数组来进行存储
    int[] recordsNumsArr = new int[26];
    //长度一致，我们分别来进行+、-操作对数组的某个索引值
    for (int i = 0; i < s.length(); i++) {
        recordsNumsArr[s.charAt(i)-'a']++;
        recordsNumsArr[t.charAt(i)-'a']--;
    }
    //来对记录字符数的数组进行遍历，一旦某个数组索引值!=0说明不有效
    for (int i = 0; i < 26; i++) {
        if(recordsNumsArr[i] != 0){
            return false;
        }
    }
    return true;
}

//优化二：添加提前结束操作
public boolean isAnagram(String s, String t) {
    if(s == null || t == null || s.length()!=t.length() || s.length() == 0){
        return false;
    }
    //使用一个数组来进行存储
    int[] recordsNumsArr = new int[26];
    for (int i = 0; i < s.length(); i++) {
        recordsNumsArr[s.charAt(i)-'a']++;
    }
    for (int i = 0; i < t.length(); i++) {
        recordsNumsArr[t.charAt(i)-'a']--;
        //提前结束：一旦在t中的某个字符相同数量>s中的
        if(recordsNumsArr[t.charAt(i)-'a'] < 0){
            return false;
        }
    }
    //来对记录字符数的数组进行遍历，一旦某个数组索引值!=0说明不有效
    for (int i = 0; i < 26; i++) {
        if(recordsNumsArr[i] != 0){
            return false;
        }
    }
    return true;
}

用Java执行的话大多数都是需要4ms，我还在想为啥只击败了45%，之后使用c语言的同样逻辑代码测了下过0ms，直接击败100%。

bool isAnagram(char *s, char *t)
{
	int i, x[26] = { 0 }, y[26] = { 0 };
	for (i = 0; s[i] != '\0'; i++)	x[s[i] - 'a']++;	//建立 s 的字符表 x
	for (i = 0; t[i] != '\0'; i++)	y[t[i] - 'a']++;	//建立 t 的字符表 y
	for (i = 0; i < 26; i++)							//比较两字符表是否相同
		if (x[i] != y[i])	return false;
	return true;										//种类、个数均相同
}

3、API

//方式一：字符数组排序比对
public boolean isAnagram(String s, String t) {
    if(s == null || t == null || s.length()!=t.length() || s.length() == 0){
        return false;
    }
    //思路：字符串s、t转成字符数组，分别进行排序，之后使用Arrays工具类进行比较
    char[] sArr = s.toCharArray();
    char[] tArr = t.toCharArray();
    Arrays.sort(sArr);
    Arrays.sort(tArr);
    return Arrays.equals(sArr,tArr);
}

//方式二：利用map集合解决
public boolean isAnagram(String s, String t) {
    if(s == null || t == null || s.length()!=t.length() || s.length() == 0){
        return false;
    }
    Map<Character,Integer> map = new HashMap<>(s.length());
    //遍历字符数组s，以key、value进行存储，key设置为字符，value则表示指定的数字
    for(char ch : s.toCharArray()){
        map.put(ch,map.getOrDefault(ch,0)+1);
    }
    //遍历字符数组t
    for(char ch : t.toCharArray()){
        Integer num = map.get(ch);
        //为null表示没有该数
        if(num == null){
            return false;
        }else if(num>1){
            map.put(ch,num-1);
        }else{ //num<=1情况，数量-1即可0，此时我们直接移除即可
            map.remove(ch);
        }
    }
    return map.isEmpty();
}

//方式三：使用strean
public boolean isAnagram(String s, String t) {
    if(s == null || t == null || s.length()!=t.length() || s.length() == 0){
        return false;
    }
    int[] numArr = new int[26];
    //这里不使用stream是因为若是转为数组还有个copy过程
    s.chars().forEach(ch->numArr[ch-'a']++);
    t.chars().forEach(ch->numArr[ch-'a']--);
    //直接对数组进行stream流操作
    return Arrays.stream(numArr).allMatch(ch->ch == 0);
}

383. 赎金信【简单】

学习：leetcode题解、代码随想录—383. 赎金信

题目链接：383. 赎金信

题目内容：

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
如果可以，返回 true ；否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。

示例 1：
输入：ransomNote = "a", magazine = "b"
输出：false

示例 2：
输入：ransomNote = "aa", magazine = "ab"
输出：false

示例 3：
输入：ransomNote = "aa", magazine = "aab"
输出：true

思路：

1、哈希解法

思路：这里题目提示说只有小写字母，可以直接通过数组来进行解决。数组对应的索引表示指定的字符，索引位置的值表示出现的次数(第一次遍历杂志字符串)，之后遍历赎金信字符串遍历的每个字符来进行抵消之前的数量。

public boolean canConstruct(String ransomNote, String magazine) {
    //若是赎金信字符串的长度大于杂志字符串，直接返回
    if(ransomNote.length() > magazine.length()){
        return false;
    }
    int[] chArray = new int[26];
    //遍历杂志字符串，对应的索引值表示该字符出现的次数
    for (char ch : magazine.toCharArray()) {
        chArray[ch-'a']++;
    }
	//遍历赎金信字符串，每个字符先判断是否存在，若是不存在直接返回，这里是否存在使用0来表示
    for (char ch : ransomNote.toCharArray()) {
        if(chArray[ch-'a'] == 0){
            return false;
        }
        chArray[ch-'a']--;
    }
    return true;
}

三数之和【中等】

学习：leetcode题解、代码随想录—第15题. 三数之和

题目地址：三数之和

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

思路：

1：定义三个指针，在一个for循环中进行，滑动窗口解法，并适当进行剪枝。

import java.util.*;
public class Solution {
    
    //思路：双指针
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>(num.length);
        //进行升序排序  [-10,0,10,20,-10,-40] =》[-40,-10,-10,0,10,20]
        Arrays.sort(num);
        //三个指针：i、left、right
        for (int i = 0; i < num.length - 2; i++) {
            //剪枝1：若是第一个值>0，后面的无需进行比对了
            if (num[i] > 0) {
                return result;
            }
            //剪枝2：若是前一个与当前一个相同，无需比较跳过该次
            if (i > 0 && num[i] == num[i-1]) {
                continue;
            }
            //设置left、right来开始比较
            int left = i + 1;
            int right = num.length - 1;
            while (left < right) {
                int val = num[i] + num[left] + num[right];
                if (val > 0) {
                    right--;
                }else if (val < 0) {
                    left++;
                }else {
                    //=0情况
                    result.add(new ArrayList(Arrays.asList(num[i], num[right], num[left])));
                    //过滤掉相同情况的left、right
                    while (left < right && num[left] == num[left+1]) left++;
                    while (left < right && num[right] == num[right-1]) right--;
                    left++;
                    right--;
                }
            }
        }
        return result;
    }
}

2、双指针优化

NO1的题解击败了85.86%，接着我就去看了效率最高的题解，然后对之前的代码进行改动，进行提前剪枝以达到优化的效果。

改动的部分在下面已经添加注释。

public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> result = new ArrayList<>(nums.length);
    Arrays.sort(nums);
    //改动1：i < nums.length-2，区间范围减小
    for (int i = 0; i < nums.length - 2; i++) {
        if (nums[i] > 0) {
            return result;
        }
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }

        //改动2：提前进行剪枝
        if (nums[i] + nums[i + 1] + nums[i + 2] > 0) {
            break;
        }

        int left = i + 1;
        int right = nums.length - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum > 0) {
                right--;
            } else if (sum < 0) {
                left++;
            } else {
                result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                while (left < right && nums[left] == nums[left + 1]) {
                    left++;
                }
                while (left < right && nums[right] == nums[right - 1]) {
                    right--;
                }
                left++;
                right--;
            }
        }
    }
    return result;
}

18. 四数之和【中等】

学习：leetcode题解、代码随想录—第18题. 四数之和

题目链接：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]]

思路：

1、双指针

思路：与三数之和的思路大致相同，只不过多加了一个指针为最后位置(不断向前移动)，中间范围中两个指针。我自制了一个动图如下：

public List<List<Integer>> fourSum(int[] nums, int target) {
    List<List<Integer>> result = new ArrayList<>(nums.length);
    Arrays.sort(nums);
    for (int i = 0; i < nums.length - 3; i++) {
        //提前剪枝，当前组合数量<4
        if(nums.length - 1 - 3 < i){
            break;
        }

        //与前面一次相同情况直接省略
        if(i>0 && nums[i] == nums[i-1]){
            continue;
        }

        if(nums[i]+nums[i+1]+nums[i+2]+nums[i+3] > target){
            break;
        }

        //后指针向前次数（与i相同区间）
        for (int j = nums.length-1; j >= i+3; j--) {

            if(j < nums.length-1 && nums[j] == nums[j+1]){
                continue;
            }

            int left = i + 1;
            int right = j - 1;
            while(left<right){
                int sum = nums[i]+nums[left]+nums[right]+nums[j];
                if(sum > target){
                    right--;
                }else if(sum < target){
                    left++;
                }else{
                    result.add(Arrays.asList(nums[i],nums[left],nums[right],nums[j]));
                    while(left<right && nums[left]==nums[left+1]){left++;}
                    while(left<right && nums[right]==nums[right-1]){right--;}
                    left++;
                    right--;
                }
            }
        }

    }
    return result;
}

454. 四数相加 II【中等】

学习：leetcode题解、代码随想录— 第454题.四数相加II

题目链接：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
解释：
两个元组如下：
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (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

思路：

1、哈希表

思路：这里的话给出了四个数组，前两组进行遍历合并存储至map中，key为合并值，value为组数，之后来遍历后两组同样求得0-(合并值)，查看是否在map中存在该key，若是存在表示组合成功，记录组合数量

public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
    Map<Integer, Integer> nums = new HashMap<>(nums1.length*nums1.length);
    int temp;
    //先对前两组数据进行存储，map中key存储两组数据某个组之和，value存储该组合出现次数
    for (int i : nums1) {
        for (int j : nums2) {
            temp = i + j;
            if (nums.containsKey(temp)) {
                nums.put(temp, nums.get(temp) + 1);
            } else {
                nums.put(temp, 1);
            }
        }
    }

    //对后两组数据进行统计符合要求的次数
    int res = 0;
    for (int i : nums3) {
        for (int j : nums4) {
            temp = i + j;
            if (nums.containsKey(0 - temp)) {
                res += nums.get(0 - temp);
            }
        }
    }
    return res;
}

2、手写Map解决

参考大佬leetcode运行效率排名超越100%代码

思路：手写一个专门针对于该题的map，该结构是数组+链表，插入数据采用头插法。实际的思路与NO1相同，时间效率优化主要就是在这个自定义map上。

//链表节点
private static class Node{
    private int val;
    private int count;
    private Node next;

    Node(int val){
        this.val = val;
        this.count = 1;
    }

    Node(int val,Node next){
        this(val);
        this.next = next;
    }
}

/**
  * Map集合，头插法
  */
private static class Map{
    Node[] table;

    public Map(int initialCapacity){
        if(initialCapacity<16){
            initialCapacity = 16;
        }else{
            //得到小于等于参数的最大2的幂   例如：7=>4，15=>8，17=>16
            initialCapacity = Integer.highestOneBit(initialCapacity);
        }
        table = new Node[initialCapacity];
    }

    private int hash(int value) {
        if (value < 0) {
            value = -value;
        }
        int h;
        return (value == 0) ? 0 : (h = value) ^ (h >>> 16);
    }

    public void put(int val){
        int tableIndex = hash(val) & table.length-1;
        Node head = table[tableIndex];
        //头节点为null情况，直接填充
        if(head == null){
            table[tableIndex] = new Node(val);
            return;
        }
        //头节点不为null情况，由于其是链表所以需要对其进行遍历比对
        Node cur = head;
        while(cur != null){
            if(cur.val == val){
                cur.count++;//若是匹配到了进行加1
                return;
            }
            cur = cur.next;
        }
        //没有匹配到，采用头插法来插入到当前数组索引下标
        table[tableIndex] = new Node(val,head);
    }

    public int getCount(int val){
        int tableIndex = hash(val) & table.length-1;
        Node head = table[tableIndex];
        if(head == null){
            return 0;
        }
        Node cur = head;
        while(cur != null){
            if(cur.val == val){
                return cur.count;
            }
            cur = cur.next;
        }
        return 0;
    }

}

public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
    Map map = new Map(nums1.length * nums2.length);
    int temp;
    for (int i : nums1) {
        for (int j : nums2) {
            temp = i+j;
            map.put(temp);
        }
    }

    int res = 0;
    for (int i : nums3) {
        for (int j : nums4) {
            temp = i+j;
            if(map.getCount(0-temp) != 0){
                res += map.getCount(0-temp);
            }
        }
    }
    return res;
}

1224. 最大相等频率【困难】

学习：题库评论区

题目链接：1224. 最大相等频率

题目内容：

给你一个正整数数组 nums，请你帮忙从该数组中找出能满足下面要求的 最长 前缀，并返回该前缀的长度：

从前缀中 恰好删除一个 元素后，剩下每个数字的出现次数都相同。
如果删除这个元素后没有剩余元素存在，仍可认为每个数字都具有相同的出现次数（也就是 0 次）。

示例 1：
输入：nums = [2,2,1,1,5,3,3,5]
输出：7
解释：对于长度为 7 的子数组 [2,2,1,1,5,3,3]，如果我们从中删去 nums[4] = 5，就可以得到 [2,2,1,1,3,3]，里面每个数字都出现了两次。

示例 2：
输入：nums = [1,1,1,2,2,2,3,3,3,4,4,4,5]
输出：13
 
提示：
2 <= nums.length <= 105
1 <= nums[i] <= 105

思路：

1、哈希表

思路：定义一个定长的数组来作为哈希表。核心就是找到符合条件的多种情况，接着关注点在最长前缀的三种情况：

情况1：举例12345，当最大频率为1,时，任意删除一个，此时即为最大前缀。
情况2：举例22331，当最大频率x最大频率出现次数=总数量-1，即为最大前缀。
情况3：举例22211，若是最大频率出现次数为1，表明当前最大频率独此一份，那么`最大频率-1=(总数量-1)/不同数字的个数``，即为最大前缀。

复杂度分析：时间复杂度O(n)；空间复杂度O(n)

class Solution {
    public int maxEqualFreq(int[] nums) {
        int[] counts = new int[100001];//前缀/子数组
        int maxCount = 0;//最大频率
        int maxCountAppearCount = 0;//最大频率出现的次数
        int valueCount = 0;//当前已经出现的不同数字个数
        int result = 0;
        for (int i = 0; i < nums.length; i++) {
            if (counts[nums[i]]++ == 0) {
                valueCount++;
            }
            //最大频率
            if (maxCount < counts[nums[i]]) {
                maxCount = counts[nums[i]];
                maxCountAppearCount = 1;
            }else if (maxCount == counts[nums[i]]) {
                maxCountAppearCount++;
            }
            //最大前缀判断
            if (maxCount == 1 ||   //当前的最大频率数量为1
                 (maxCount * maxCountAppearCount == i) ||  //最大频率*最大频率出现的次数若是为真实个数-1
                 (maxCountAppearCount == 1 && maxCount - 1 == i / valueCount)) {  //出现数字最大频率的个数为1时，只需要删除一个，其他所有数字出现次数一样为maxCount-1
                result = i + 1;
            }
        }
        return result;

    }
}

前言

哈希表基础知识

基本概念

最简单哈希：字符哈希

Hash表的实现（手写Map）

HashMap 基本使用

剑指offer

剑指 Offer 03. 数组中重复的数字【简单】

剑指 Offer 50. 第一个只出现一次的字符【简单】

剑指 Offer 53 - I. 在排序数组中查找数字【简单】

剑指 Offer 57. 和为s的两个数字【简单】

剑指 Offer 61. 扑克牌中的顺子【简单】

剑指 Offer 56 - I. 数组中数字出现的次数【中等，等同牛客第3题】

剑指 Offer 56 - II. 数组中数字出现的次数 II【中等】

剑指 Offer 35. 复杂链表的复制【中等】

剑指 Offer II 004. 只出现一次的数字【中等】

剑指 Offer II 070. 排序数组中只出现一次的数字【中等】

牛客

两数之和【简单】

数组中出现次数超过一半的数字是【简单】

数组中只出现一次的两个数字【中等，重点】

缺失的第一个正整数【中等】

leetcode

202. 快乐数【简单】

1. 两数之和【简单】

349. 两个数组的交集【简单】

169. 多数元素【简单】

448. 找到所有数组中消失的数字【简单】

242. 有效的字母异位词【简单】

383. 赎金信【简单】

三数之和【中等】

18. 四数之和【中等】

454. 四数相加 II【中等】

1224. 最大相等频率【困难】

评论区请在客户端页面查看