理论基础

哈希

哈希（Hash）是一个广泛应用于数据结构和算法中的概念，主要用于快速查找、存储和比较数据。

哈希的核心在于哈希函数（Hash Function），它将输入（通常称为键，key）映射到一个固定范围的输出值，这个输出值称为哈希值（Hash Value）或哈希码（HashCode）。

哈希的目的在于将原本复杂、不规则的数据转化为简洁的、固定长度的值，使得数据的存储和检索更加高效。

常见的三种哈希结构

HashTable

哈希表是根据关键码的值而直接进行访问的数据结构。

其实直白来讲其实数组就是一张哈希表。哈希表中关键码就是数组的索引下标，然后通过下标直接访问数组中的元素，如下图所示：

哈希表1

一般哈希表都是用来快速判断一个元素是否出现集合里。例如要查询一个名字是否在这所学校里。要枚举的话时间复杂度是O(n)，但如果使用哈希表的话，只需要O(1)就可以做到。

只需要初始化把这所学校里学生的名字都存在哈希表里，在查询的时候通过索引直接就可以知道这位同学在不在这所学校里了。

HashMap

Java中的HashMap是一个实现Map接口的类，它提供了一个存储键值对（key-value pairs）的数据结构。HashMap允许使用唯一的键来映射到特定的值，并且能够高效地进行插入、删除和查找操作。键值对之间没有特定的顺序，HashMap也不是线程安全的。

关键特性和内部工作原理的详细说明：

特性：

键值关联：HashMap存储的是键值对，其中键是唯一的，而值可以重复。
无序性：HashMap中的元素没有特定的顺序，迭代时的顺序并不反映插入时的顺序。
允许null值和null键：HashMap是少数几个可以接受null键和null值的Java集合之一，但每个HashMap只能有一个null键。
线程不安全：HashMap不是线程安全的，多线程环境下若不采取额外的同步措施，可能导致数据不一致性。
可调整大小：随着元素的增加，HashMap会自动扩容来维持其性能，通过重新哈希所有元素到更大的数组中实现。
性能：平均情况下，HashMap提供O(1)的时间复杂度进行插入、删除和查找操作。

应用场景：

缓存：HashMap非常适合做轻量级的缓存，快速存取热点数据。
数据映射：在需要快速根据键查找相关联值的场景，如配置参数管理。
计数：可以用HashMap统计元素出现的频率，键是元素，值是出现次数。
去重：虽然HashSet更直接，但在需要存储额外信息或自定义比较逻辑时，HashMap可以用来去重。
图的邻接表表示：在图算法中，HashMap可以用来表示顶点的邻接关系，键是顶点，值是一个列表或集合，包含与该顶点相邻的所有顶点。

HashSet

Java中的HashSet是一个实现了Set接口的集合类，它提供了一种存储不可重复元素的高效数据结构。HashSet的实现基于HashMap，这意味着它内部使用了哈希表来管理元素，这使得HashSet能够提供快速的插入、删除和查找操作。

为了确保HashSet能正确识别重复元素，存储在HashSet中的自定义对象必须正确重写equals()和hashCode()方法，保证相等的对象具有相同的哈希值，并且通过equals()方法判断也为相等。

以下是关于HashSet的一些关键特性和内部工作原理的详细说明：

特性：

无序性：HashSet不保证元素的插入顺序，每次遍历HashSet时，元素的顺序可能不同。这是因为HashSet在内部使用哈希表，元素的存储位置由其哈希值决定。
不允许重复：HashSet中不能包含重复的元素。这是通过比较元素的哈希值以及equals()方法来实现的。如果两个元素的哈希值相同，并且通过equals()方法比较也认为是相等的，则视为重复元素，后者将不会被加入集合中。
允许null值：HashSet允许存储一个null元素，因为HashMap允许一个键为null。
非线程安全：HashSet不是线程安全的。如果多个线程同时访问一个HashSet，且至少有一个线程修改了HashSet，则必须通过外部同步来保证线程安全。

举例：

import java.util.HashSet;
 
public class HashSetExample {
    public static void main(String[] args) {
        // 创建一个HashSet实例
        HashSet<String> myHashSet = new HashSet<>();
 
        // 添加元素
        myHashSet.add("Apple");
        myHashSet.add("Banana");
        myHashSet.add("Cherry");
        System.out.println("HashSet after adding elements: " + myHashSet);
 
        // 检查元素是否存在
        boolean isPresent = myHashSet.contains("Banana");
        System.out.println("Is 'Banana' in the HashSet? " + isPresent);
 
        // 尝试添加重复元素
        myHashSet.add("Apple");
        System.out.println("HashSet after trying to add duplicate 'Apple': " + myHashSet);
        
        // 删除元素
        boolean isRemoved = myHashSet.remove("Banana");
        System.out.println("Is 'Banana' removed? " + isRemoved);
        System.out.println("HashSet after removing 'Banana': " + myHashSet);
 
        // 遍历HashSet
        System.out.println("Iterating over HashSet:");
        for (String fruit : myHashSet) {
            System.out.println(fruit);
        }
        
        // 清空HashSet
        myHashSet.clear();
        System.out.println("HashSet after clearing: " + myHashSet);
    }
}

关于hashCode()方法

作用：Java中的每个对象都继承自Object类，而Object类有一个hashCode()方法，这个方法被设计用来返回对象的哈希码。默认的hashCode()实现通常基于对象的内存地址，但子类通常会重写此方法，以便根据对象的实际内容生成更有意义的哈希值。

在Object类中，hashCode()方法的默认实现是根据对象的内存地址计算得到的哈希码。换句话说，如果两个对象在内存中的地址不同，那么它们的哈希码就也会不同。

hashCode()方法返回对象的哈希码值（哈希码），是一个int类型的整数。哈希码是根据对象的内存地址或者根据对象的内容计算得到的一个唯一标识符。在Java中，hashCode()方法通常与equals()方法一起使用，用于判断两个对象是否相等。

重写规则：在自定义类中，通常需要重写hashCode()方法，以便根据对象的内容来生成哈希码，而不是依赖于默认的内存地址。
如果重写了equals()方法，就应该同时重写hashCode()方法，保证相等的对象拥有相等的哈希码。

哈希值虽然可以用于快速比较，但不保证绝对唯一，因此在判断对象相等时，除了比较哈希值外，还需要通过equals() 方法比较对象的实际内容。在实现自定义类的hashCode()时，应当遵守与equals()方法的一致性原则，即如果两个对象通过equals()判断为相等，它们的哈希码也必须相等。反之，哈希码相等的对象不一定通过equals()判断相等。

重写hashCode()方法时，应该遵循以下规则：

相等的对象必须具有相等的哈希码。
不相等的对象尽量产生不同的哈希码，以减少哈希冲突的发生。

哈希函数

数据映射到哈希表上涉及到了hash function ，也就是哈希函数。

把学生的姓名直接映射为哈希表上的索引，然后就可以通过查询索引下标快速知道这位同学是否在这所学校里了。

哈希函数如下图所示，通过hashCode把名字转化为数值，一般hashcode是通过特定编码方式，可以将其他数据格式转化为不同的数值，这样就把学生名字映射为哈希表上的索引数字了。

哈希函数应该是高效的，计算速度快，且应该尽量均匀分布，以减少哈希冲突。

哈希表2

哈希冲突

如果学生的数量大于哈希表的大小，此时就算哈希函数计算的再均匀，也避免不了会有几位学生的名字同时映射到哈希表同一个索引下标的位置。

如图所示，小李和小王都映射到了索引下标 1 的位置，这一现象叫做哈希冲突。

哈希表3

解决哈希碰撞方法非常多，这里简写两种常见解决方法，拉链法和线性探测法。

拉链法

刚刚小李和小王在索引1的位置发生了冲突，发生冲突的元素都被存储在链表中。这样我们就可以通过索引找到小李和小王了

哈希表4

（数据规模是dataSize，哈希表的大小为tableSize）

其实拉链法就是要选择适当的哈希表的大小，这样既不会因为数组空值而浪费大量内存，也不会因为链表太长而在查找上浪费太多时间。

线性探测法

使用线性探测法，一定要保证tableSize大于dataSize。我们需要依靠哈希表中的空位来解决碰撞问题。

例如冲突的位置，放了小李，那么就向下找一个空位放置小王的信息。所以要求tableSize一定要大于dataSize ，要不然哈希表上就没有空置的位置来存放冲突的数据了。如图所示：

哈希表5

总结

当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。

但是哈希法也是牺牲了空间换取了时间，因为我们要使用额外的数组，set或者是map来存放数据，才能实现快速的查找。

有效的字母异位词

242.有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

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

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

说明: 你可以假设字符串只包含小写字母。

思路

定义一个数组record用来上记录字符串s里字符出现的次数。

需要把字符映射到数组也就是哈希表的索引下标上，因为字符a到字符z的ASCII是26个连续的数值，所以字符a映射为下标0，相应的字符z映射为下标25。

再遍历字符串s的时候，只需要将 s[i] - ‘a’ 所在的元素做+1 操作即可，并不需要记住字符a的ASCII，只要求出一个相对数值就可以了。 这样就将字符串s中字符出现的次数统计出来了。

那看一下如何检查字符串t中是否出现了这些字符，同样在遍历字符串t的时候，对t中出现的字符映射哈希表索引上的数值再做-1的操作。

那么最后检查一下，record数组如果有的元素不为零0，说明字符串s和t一定是谁多了字符或者谁少了字符，return false。

最后如果record数组所有元素都为0，说明字符串s和t是字母异位词，return true。

时间复杂度为O(n)，空间上因为定义是的一个常量大小的辅助数组，所以空间复杂度为O(1)。

public boolean isAnagram(String s, String t) {
    int[] record = new int[26]; // 创建一个长度为 26 的数组，用来记录每个字母的出现次数

    // 遍历字符串 s，将字符映射为数组索引 0 到 25，增加该字符的计数
    for (int i = 0; i < s.length(); i++) {
        record[s.charAt(i) - 'a']++; 
    }

    // 遍历字符串 t，同样操作，减少对应字符的计数
    for (int i = 0; i < t.length(); i++) {
        record[t.charAt(i) - 'a']--; 
    }

    // 检查 record 数组中的所有值是否都为 0
    // 如果某个字符的计数不为 0，说明两个字符串的字符组成不同
    for (int count: record) {
        if (count != 0) { 
            return false; 
        }
    }

    return true; // 如果所有字符计数都为 0，说明是字母异位词
}

类似题目

383.赎金信

这个题主要是理解题意，就是ransomNote里的所有字符必须是被magazine所包含的，所以我们把26个英文字母字符映射到一个26位的数组上。分别操作这两个字符串。

合法的ransomNote里存在的每个字符的数量，都一定小于magazine中存在的相应字符的数量。

换句话说，这个ransomNote不能把magazine取空了，都要大于0才行。所以每一位上都要有(count >= 0) 。

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] record = new int[26];  // 用来记录 'a' 到 'z' 字母的计数

        for (int i = 0; i < ransomNote.length(); i++) {
            record[ransomNote.charAt(i) - 'a']--;
        }

        for (int i = 0; i < magazine.length(); i++) {
            record[magazine.charAt(i) - 'a']++;  
        }

        for (int count: record) {
            if (count < 0) { 
                return false;
            }
        }

        return true;  
    }
}

49.字母异位词分组

这个题是需要把字符串数组里的字母异位词全都组合在一起，然后以列表的形式输出。就是说，每一组字母异位词都可以被视作一个特殊的集合。

我们知道，当遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。

遍历 strs 数组中的每一个字符串，然后把这个字符串转换为字符数组，进行一个sort的排序，这样所有的字母异位词都会呈现一个同一的形态，我们把它作为这个HashMap的key。

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        // 创建一个 HashMap，键是排序后的字符串，值是一个 List，存放所有与该键相同的字母异位词
        Map<String, List<String>> theHash = new HashMap<>();

        // 遍历 strs 数组中的每一个字符串
        for (var str : strs) {
            // 将字符串转换为字符数组
            char[] charArray = str.toCharArray();
            
            // 对字符数组进行排序
            Arrays.sort(charArray);
            
            // 将排序后的字符数组转换为字符串
            String sortedStr = new String(charArray);

            // 如果 theHash 中没有 sortedStr 作为键，
            // 则创建一个新的空 ArrayList 因为需要填补原字符串
            if (!theHash.containsKey(sortedStr)) {
                theHash.put(sortedStr, new ArrayList<>());
            }
            
            // 将原字符串添加到 sortedStr 对应的 List 中
            theHash.get(sortedStr).add(str);
        }

        // 返回 theHash 中所有值的 List，也就是所有字母异位词的分组
        return new ArrayList<>(theHash.values());
    }
}

438.找到字符串中所有字母异位词

就是找到字符串P里存在的所有S的字母异位词，返回这些子串的起始索引。

首先，这些字母异位词的长度一定是和P一样的。这是一个固定长度的窗口。

就不断比较这个窗口里的部分P和S，找到了就把下标计入。

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        
        if (s == null || p == null || s.length() < p.length()) {
            return result;
        }
        
        // 设置 p 和窗口的字符频率
        int[] pCount = new int[26];  
        int[] windowCount = new int[26];  
        
        // 统计 p 的字符频率
        for (char c : p.toCharArray()) {
            pCount[c - 'a']++;
        }
        
        // 初始窗口
        for (int i = 0; i < p.length(); i++) {
            windowCount[s.charAt(i) - 'a']++;
        }
        
        // 检查初始窗口
        if (matches(pCount, windowCount)) {
            result.add(0);
        }
        
        // 滑动窗口
        for (int i = p.length(); i < s.length(); i++) {
            // 添加新字符
            windowCount[s.charAt(i) - 'a']++;
            // 移除旧字符
            windowCount[s.charAt(i - p.length()) - 'a']--;
            
            // 检查当前窗口
            if (matches(pCount, windowCount)) {
                result.add(i - p.length() + 1);
            }
        }
        
        return result;
    }
    
    // 判断两个字符频率数组是否相同
    private boolean matches(int[] pCount, int[] windowCount) {
        for (int i = 0; i < 26; i++) {
            if (pCount[i] != windowCount[i]) {
                return false;
            }
        }
        return true;
    }
}

两个数组的交集

349. 两个数组的交集

给定两个数组 nums1 和 nums2 ，返回它们的交集。

输出结果中的每个元素一定是唯一的。我们可以 不考虑输出结果的顺序 。

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

示例 2：

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的

提示：

1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000

思路

数组

设置两个数组，分别表示nums1和nums2的哈希。避免哈希冲突，数组的长度是nums的长度。

查找数组nums1和nums2中的数，更新hash1和hash2。

最后遍历一次，将hash1和hash2中都大于0的数加入数组输出。

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        int[] hash1 = new int[1001];
        int[] hash2 = new int[1001];

        for(int i : nums1)
            hash1[i]++;
        for(int i : nums2)
            hash2[i]++;

        List<Integer> resList = new ArrayList<>();

        for(int i = 0; i < 1001; i++)
            if(hash1[i] > 0 && hash2[i] > 0)
                resList.add(i);

        int index = 0;
        int res[] = new int[resList.size()];
        for(int i : resList)
            res[index++] = i;
        return res;
    }
}

set

使用数组来做哈希的题目，是因为题目都限制了数值的大小。而且如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。

这一题更好的方法是使用set，因为已知输出结果中的每个元素一定是唯一的，而且我们可以不考虑输出结果的顺序。

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

        for (int i : nums1) {
            set1.add(i);
        }

        for (int i : nums2) {
            if (set1.contains(i)) {
                result.add(i);
            }
        }
        
        //申请一个数组存放setRes中的元素,最后返回数组
        int[] arr = new int[result.size()];
        int j = 0;
        for(int i : result){
            arr[j++] = i;
        }
        
        return arr;
    }
}

类似题目

350.两个数组的交集 II

快乐数

202.快乐数

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。如果可以变为 1，那么这个数就是快乐数。

如果 n 是快乐数就返回 True ；不是，则返回 False 。

示例：

输入：19
输出：true
解释：
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

思路

这道题只有两种结束条件：

这个数最终变成了1；
这个数无限循环，sum会重复出现；

所以这道题目使用哈希法，来判断这个sum是否重复出现，如果重复了就是return false，否则一直找到sum为1为止。

class Solution {
    public boolean isHappy(int n) {
        Set<Integer> record = new HashSet<>();
        while(n != 1 && !record.contains(n) ){
            record.add(n);
            n = getNextNumber(n);
        }
        return n == 1;
    }

    private int getNextNumber(int n) {
        int res = 0;
        while(n>0){
            res += (n % 10)*(n % 10);
            n /= 10; 
        }
        return res;
    }
}

两数之和

梦开始的地方。这一次我们使用哈希。

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]

提示：

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案

思路

暴力

附上我2022.11.21的python代码，第一次AC，一切都从这里开始。

class Solution(object):
    def twoSum(self,nums, target):
        lens = len(nums)
        j=-1
        for i in range(lens):
            if (target - nums[i]) in nums:
                if (nums.count(target - nums[i]) == 1)&(target - nums[i] == nums[i]):
                    continue
                else:
                    j = nums.index(target - nums[i],i+1)                
                    break
        if j>0:
            return [i,j]
        else:
            return []

哈希

原先的解法是循环嵌套，使用哈希表的话，可以让查询的时间复杂度从O(n)缩减到O(1)。

这里的思路是把已经遍历过的元素的值与下标都放在一个HashMap里。每遍历到一个新的位置，就会在HashMap里查找这些遍历过的元素中，是否存在可以满足条件的元素。使用containsKey( )就可以搞定，这样查询的时间复杂度缩减到O(1)。

四个重点内容：

为什么会想到用哈希表？

当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就可以使用哈希法。这里的情况是我们需要找到一个和新位置元素匹配的值，要有一个集合来存放我们遍历过的元素，然后在遍历数组的时候去访问这个集合获知某元素是否遍历过，也就是是否出现在这个集合。正好使用哈希表。
哈希表为什么用map？

因为我们不仅需要储存值，还需要记录下标。
本题map是用来存什么的？

map目的用来存放我们访问过的元素，因为遍历数组的时候，需要记录我们之前遍历过哪些元素和对应的下标，这样才能找到值相加等于target的目标元素，返回下标。
map中的key和value用来存什么的？

因为我们需要判断这个元素是否出现过，如果出现过，返回这个元素的下标。那么判断元素是否出现，这个元素就要作为key，所以数组中的元素作为key，有key对应的就是value，value用来存下标。

class Solution {
    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<>();
        for(int i =0;i< nums.length;i++){
            int temp = target - nums[i];
            if(map.containsKey(temp)){
                res[1] = i;
                res[0] = map.get(temp);
            }
            map.put(nums[i],i);
        }
        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

思路

这个题要求是在四个长度一致的数组里各抽取一个元素出来，然后这些元素之和为0。

如果是一个四层循环，我们的时间开销会直接爆炸成O(n^4)，是无法通过的。这道题需要采取用空间换时间的办法，这也是哈希表的功能之一。

先求nums1，nums2所有情况的和，这样时间复杂度来到了 O(n^2)，把这些和全都塞进一个HashMap里作为key，value则是特定的和出现的次数。

接下来求num3，num4所有情况的和，这样时间复杂度也还是 O(n^2)，查找map里有没有数正好是跟num3，num4之和相加为0的。也就是查找- (i + j) 所对应的value，然后遍历完成后作为答案输出即可。

时间复杂度: O(n^2)

空间复杂度: O(n^2)，最坏情况下A和B的值各不相同，相加产生的数字个数为 n^2

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        int res = 0;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i : nums1) 
            for (int j : nums2) 
                map.put(sum, map.getOrDefault(i + j, 0) + 1);


        for (int i:nums3)
            for(int j:nums4)
                res += map.getOrDefault(-(i+j) , 0);


        return res;
    }
}

水果成篮

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果种类。

你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：

你只有两个篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
你可以选择任意一棵树开始采摘，你必须从每棵树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。

给你一个整数数组 fruits ，返回你可以收集的水果的最大数目。

示例 1：

输入：fruits = [1,2,1]
输出：3
解释：可以采摘全部 3 棵树。

示例 2：

输入：fruits = [0,1,2,2]
输出：3
解释：可以采摘 [1,2,2] 这三棵树。
如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。

思路

题目翻译成人话就是：找至多包含两种元素的最长子串，返回其长度。

我们的思路是通过滑动窗口不断扩展子串的长度，通过 left 和 right 两个指针来表示当前的窗口区间。right 指针从左到右遍历数组，而 left 指针用于收缩窗口。确保窗口内的水果种类不超过两种。

为了维护窗口区间，我们需要记录窗口内每种水果的数量。一旦超过两种，我们会收缩区间到合法范围内。这里我们使用HashMap实现，因为这样我们的储存，查询操作都会简化为O(1)的时间复杂度，而且可以同时储存水果的种类和个数，方便管理。在调整窗口时，就不断减少 left 指针指向的水果的计数，直到该水果的计数变为 0，就相当于从哈希表中移除该水果种类，并且左指针 left 接着向右移动，继续收缩窗口。在每次调整窗口后，更新 maxFruits 为当前窗口大小，即 right - left + 1。这是HashMap的典型表现形式。

整个过程中的每个元素最多被 right 和 left 两个指针各访问一次，所以时间复杂度为 O(n)。

public class Solution {
    public int totalFruit(int[] fruits) {
        // 用哈希表来记录窗口内每种水果的数量
        HashMap<Integer, Integer> map = new HashMap<>();
        int left = 0; // 左指针
        int maxFruits = 0; // 最大水果数
        
        // 遍历整个数组
        for (int right = 0; right < fruits.length; right++) {
            // 将右指针指向的水果加入窗口
            map.put(fruits[right], map.getOrDefault(fruits[right], 0) + 1);
            
            // 如果窗口内有超过两种水果，调整左指针
            while (map.size() > 2) {
                int leftFruit = fruits[left];
                map.put(leftFruit, map.get(leftFruit) - 1);
                if (map.get(leftFruit) == 0) {
                    map.remove(leftFruit); // 移除水果种类
                }
                left++; // 收缩窗口
            }
            
            // 更新最大水果数
            maxFruits = Math.max(maxFruits, right - left + 1);
        }
        
        return maxFruits;
    }
}

算法笔记-哈希

理论基础

哈希

常见的三种哈希结构

HashTable

HashMap

HashSet

关于hashCode()方法

哈希函数

哈希冲突

拉链法

线性探测法

总结

有效的字母异位词

思路

类似题目

两个数组的交集

思路

数组

set

类似题目

快乐数

思路

两数之和

思路

暴力

哈希

四数相加

思路

水果成篮

思路