LeetCodeHot100_0x01

1. 两数之和

解题思路： 暴力枚举法、哈希法
【暴力枚举】

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

【哈希法】要找 x + y = targer,则对于每一个x，只需要用哈希判断存不存在 y = targer - x；

java">class Solution {
    public int[] twoSum(int[] nums, int target) {
        // 存储值（键） + 下标
        Map<Integer,Integer> hs = new HashMap<>();
        for(int i=0;i<nums.length;i++) {
            // containsKey 方法用于寻找键是否存在
            if(hs.containsKey(target-nums[i])) {
                return new int[]{i,hs.get(target-nums[i])};
            }
            // 将当前映射哈希表
            hs.put(nums[i],i);
        }
        return new int[0];
    }
}

复习： HashMap数据结构、常用方法、使用场景

一、底层数据结构

• HashMap 的底层由 数组 + 链表 + 红黑树 组成，核心设计目标是解决哈希冲突并保证高效操作。
• 数组：默认长度16，长度始终是2的幂次方，每个元素都是一个桶，上面连接着链表或红黑树
• 链表：解决哈希冲突，使用链地址法（尾插法避免并发场景死循环）
• 红黑树：链表长度大于8转换，小于6退化。用于优化查询效率：O(n) —> O(logn)

---

二、常用方法

java">Map<R,V> hs = new HashMap<R,V>(); // 声明
put(K key, V value)     // 添加键值对
get(K key)                   // 获取值
containsKey(K key)      // 判断键是否存在
keySet()                // 获取所有键的集合
values()                // 获取所有值的集合
entrySet()              // 获取所有键值对
getOrDefault(K key, V defaultValue) // 安全获取值

---

三、使用场景： 快速插入/查询、统计频率

---

2. 字母异位词分词

解题思路： 将字符串排序后作为哈希的键，值则为已经符合的字符串列表
【哈希法】关键在于如何对字符串进行排序、如何更新已有的字符串列表

java">class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        // 排序后作为哈希的键,值为存储相同的字符串列表
        Map<String,List<String>> hs = new HashMap<>();
        for(String str : strs) {
            // 取出字符串进行排序
            char[] str_ = str.toCharArray();
            Arrays.sort(str_);
            String key = new String(str_);
            // 取出该键中已有的字符串列表
            // 这里犯了一个错，这个列表可能是空的，后面会报错，需要用getOrDefault方法安全取值
            // List<String> str_list = hs.get(key);
            List<String> str_list = hs.getOrDefault(key,new ArrayList<>());
            str_list.add(str);
            hs.put(key,str_list);
        }
        List<List<String>> resList = new ArrayList<>(hs.values());
        return resList;
    }
}

复习： 对字符串进行排序思路

对字符串内的字符排序（例如将 “cab” 排序为 “abc”）
方法 1：字符数组排序（最常用）

java">String str = "cab";
char[] chars = str.toCharArray();
Arrays.sort(chars); // 默认升序排序
String sortedStr = new String(chars); // "abc"

---

方法 2：使用 Java 8 Stream API

java">String str = "cab";
String sortedStr = str.chars() // 转为 IntStream
   .sorted() // 对字符的 Unicode 值排序
  .collect(
       StringBuilder::new,
       StringBuilder::appendCodePoint,
     StringBuilder::append
).toString(); // "abc"

---

方法 3：转换为列表排序

java">String str = "cab";
List<Character> charList = new ArrayList<>();
for (char c : str.toCharArray()) {
   charList.add(c);
}
Collections.sort(charList); // 升序排序
StringBuilder sb = new StringBuilder();
for (Character c : charList) {
   sb.append(c);
}
String sortedStr = sb.toString(); // "abc"

---

3. 最长连续序列

解题思路： 用哈希存下来，然后遍历哈希列表，找到最长连续的序列，其长度就是答案
【哈希法】

java">class Solution {
    public int longestConsecutive(int[] nums) {
        // 哈希 ---> Set版去重
        Set<Integer> hs = new HashSet<>();
        for(int num : nums) {
            // 加入哈希
            hs.add(num);
        }

        int res = 0;    // 记录答案
        for(int num : hs) {
            // 查看hs中有多少个连续的值
            if(!hs.contains(num-1)) { // 重新规划起点
                int currN = num;
                int currC = 1;
                // 开始匹配
                while(hs.contains(currN + 1)) {
                    currN ++;
                    currC ++;
                }
                res = Math.max(res,currC);
            } 
        }
        return res;
    }
}

【动态规划法】定义动规：fn[i] : 以第i个元素结尾的最大值，转移存在以下关系：

• ==1 : fn[i] = fn[i-1] + 1;
• ==0 : fn[i] = fn[i-1];
• order : fn[i] = 1;

java">class Solution {
    public int longestConsecutive(int[] nums) {
        // 排序 + 动态规划
        //1. 排除边界值
        if(nums.length == 1) return 1;
        if(nums.length == 0) return 0;
        //2. 排序
        Arrays.sort(nums);
        //3. 定义动规方程意义(fn[i] 以第i个元素结尾中最大的连续值长度)
        int []fn = new int[nums.length];
        //4. 初始化值
        fn[0] = 1;
        int res = fn[0];
        //5. 遍历更新方程
        for(int i=1;i<nums.length;i++) {
            if(nums[i] - nums[i-1] == 1) {
                fn[i] = fn[i-1] + 1; 
            }else if(nums[i] == nums[i-1]) {
                fn[i] = fn[i-1];
            }else {
                fn[i] = 1;
            }
            res = Math.max(res,fn[i]);
        }
        return res;
    } 
}

复习： HashSet常用方法

HashSet（基于 HashMap）
特点：无序，插入/查询 O(1)
常用方法：

java">add(E e)                // 添加元素
remove(Object o)        // 删除元素
contains(Object o)      // 是否包含元素

---

2. TreeSet（基于 TreeMap）
   特点：元素有序（自然排序或自定义 Comparator），插入/查询 O(log n)
   特有方法：

java">first(), last()         // 最小/最大元素
ceiling(E e), floor(E e) // 类似 TreeMap

---

4. 移动零

解题思路： 整体向前偏移，在最后补若干零

java">class Solution {
    public void moveZeroes(int[] nums) {
        // 整体偏移
        int i = 0;  // 记录非零值指针
        // 将前面变成非零，后面变成0
        for(int j=0;j<nums.length;j++) {
            if(nums[j] != 0) nums[i++] = nums[j];
        }
        for(int k = i;k<nums.length;k++) {
            nums[k] = 0;
        }
    }
}

---

5、盛最多水的容器

解题思路： 双指针，不断缩小容器宽度，记录过程中的最优解
【双指针法】：关键：移动策略：哪边短移动哪边。

java">class Solution {
    public int maxArea(int[] height) {
        // 认识：（长 * 宽）Max、木桶效应
        // 双端指针，靠近过程必然宽会变小，长要扩大才有最优
        // 移动那边？肯定是短板的一端移动更优
        int len = height.length;
        int res = (len-1) * Math.min(height[0] ,height[len-1]);
        int i=0,j=len-1;
        while(i<j) {
            if(height[i] >= height[j]) j--;
            else i++;

            int temp = (j-i)*Math.min(height[i],height[j]);
            res = Math.max(res,temp);
        }
        return res;
    }
}

---

6、三数之和（不熟）

解题思路： 使用暴力法无法通过，遇到了时间复杂度问题过高。正确的做法因该是用双指针
【暴力法】超出时间限制 308 / 313 个通过的测试用例

• 首先通过排序将重复项聚集，便于后续去重；接着通过三重循环枚举所有不重复的三元组。

java">class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        // 排序 + 暴力枚举所有可能
        List<List<Integer>> reslist = new ArrayList<>();
        Arrays.sort(nums);
        for(int i=0;i<nums.length-2;i++) {
            // 去重1：
            if(i>0 && nums[i] == nums[i-1])continue;
            for(int j=i+1;j<nums.length-1;j++) {
                // 去重2：
                if(j>i+1 && nums[j] == nums[j-1]) continue;
                for(int k=j+1;k<nums.length;k++) {
                    // 去重3：
                    if(k >j+1 && nums[k] == nums[k-1]) continue;
                    if(nums[i] + nums[j] + nums[k] == 0) {
                        reslist.add(Arrays.asList(nums[i],nums[j],nums[k]));
                    } 
                }
            }
        }
        return reslist;
    }
}

【双指针法】

• 三重循环枚举a+b+c==0，在确定a、b后，c只有唯一的一个值
• 在确定a后，那么 b + c = -a，也就是说b越大，c越小，两者存在一个关系
• 于是对于第二重循环和第三重循环，我们可以利用双端指针来寻找在a固定下符合的所有b、c集合

java">class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        // 排序+ 双指针枚举
        List<List<Integer>> reslist = new ArrayList<>();
        Arrays.sort(nums);
        int n = nums.length;
        for(int a=0;a<n;a++) {
            // 去重
            if(a>0 && nums[a] == nums[a-1]) continue;
            for(int b=a+1,c=n-1;b<n-1;b++){
                // 去重
                if(b > a+1 && nums[b] == nums[b-1])continue;
                // 枚举符合条件的c(c是从大到小枚举的，界限是直到小于就不符合了)
                while(c>b && nums[b] + nums[c] > -nums[a])c--;
                if(c==b)break;  // 找不到
                if(nums[a] + nums[b] + nums[c] ==0)
                    reslist.add(Arrays.asList(nums[a],nums[b],nums[c]));
            }
        }
        return reslist;
    }
}

---

7、接雨水（不会）

求解思路： 提前预处理出当前位置的左边最高高度、右边最高高度，然后与当前位置高度差就是当前位置能够储存水的量。再求和。

java">class Solution {
    public int trap(int[] height) {
        // 这道题目理解完其实不难了，关键你要明白一个问题：i位置的雨水量怎么算？
        // 取决于（i左边最高 ，i右边最高）min【木桶效应】，记为H
        // i位置的高度h
        // i位置能储水 H-h
        // 所以关键在于如何快速的找到i左边、右边的最高高度---提前预处理出来
        int n = height.length;
        if(n==0) return 0;
        int[] leftMax = new int[n];
        int[] rightMax = new int[n];
        leftMax[0] = height[0];rightMax[n-1]=height[n-1];

        for(int i=1;i<n;i++) {
            leftMax[i] = Math.max(leftMax[i-1],height[i]);
        }
        for(int i=n-2;i>=0;i--){
            rightMax[i] = Math.max(rightMax[i+1],height[i]);
        }

        // 计算每一格可以存水量
        int res = 0;
        for(int i=0;i<n;i++) {
            res += Math.min(leftMax[i],rightMax[i]) - height[i];
        }
        return res;
    }
}

---

8、无重复字符的最长子串

解题思路： 遍历枚举开头，用哈希表判断过程中符合的最长子串
【哈希法】O(N^2)复杂度，还是不太优美

java">class Solution {
    public int lengthOfLongestSubstring(String s) {
        // 用哈希来判断字符串有没有重复
        if(s.length() < 2) return s.length();
        int res = 1;
        for(int i=0;i<s.length();i++) {
        //	每次循环都定义一个哈希表，用来判断什么时候出现重复的字符，则该长度终止
            Map<Character,Boolean> hm = new HashMap<>();
            hm.put(s.charAt(i),true);
            int temp = 1;
            for(int j=i+1;j<s.length();j++) {
            	// 判断是否存在当前键
                if(hm.containsKey(s.charAt(j))) {
                    break;
                }else {
                    temp++;
                    hm.put(s.charAt(j),true);
                }
            }
            res = Math.max(res,temp);
        }
        return res;
    }
}

【滑动窗口法】优化思路：假设从k到第rk个元素才发生重复冲突，那么k+1到第rk元素定然没有冲突，我们就可以继续向右扩展，直到出现冲突。重复以往。这个思路的好处是利用公共并不冲突的位置减少了很多判断过程，类似一个滑动的窗口一样。只需要一次遍历就可以得到答案。

java">class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        if(n<2)return n;
        // 滑动窗口
        Set<Character> hs = new HashSet<>();
        
        int j = 0, res = 1; // 定义右指针，初始值为-1
        for(int i=0;i<n;i++) {
        	// 左边指针右移，跳一个 
            if(i != 0) {
                hs.remove(s.charAt(i-1));
            }
            // 右移指针直到出现冲突
            while(j<n && !hs.contains(s.charAt(j))) {
                hs.add(s.charAt(j));
                j++;
            }
            // 更新答案
            res = Math.max(res,j-i);
        }
        return res;
    }
}

---

9、找到字符串中所有字母异位词 (不熟)

解题思路： 这题的解题思路几乎和我想的一样，滑动窗口 + 哈希表维护。需要学习的是它的代码思路，通过Arrays工具类中的equals方法可以快速判断两个数列是否完全相同，真是让我学了一招，这样的话，我们利用数组将字符串p中的字符组成拷贝下来，在维护窗口的过程中，判断更新的s的子串是否也是与p相同的字符组成，是则代表该字符串的开头就是一个答案。

java">class Solution {
    public List<Integer> findAnagrams(String s, String p) {

        // 滑动窗口 + 数组哈希
        int[] Scnt = new int[26];
        int[] Pcnt = new int[26];
        int size = p.length();
        int n = s.length();
        if(n < size) return new ArrayList<Integer>();
        List<Integer> res = new ArrayList<>();
        
        for(int i=0;i<size;i++) {
            Scnt[s.charAt(i)-'a']++;
            Pcnt[p.charAt(i)-'a']++;
        }

        // （不要漏了！！）判断开头是不是原本就符合要求的
        if(Arrays.equals(Scnt,Pcnt)) {
            res.add(0);
        }

        for(int i=0;i<n-size;i++) { // 枚举当前需要删除的窗口左值
            Scnt[s.charAt(i)-'a']--;    // 滑动窗口维护左边的字符对应的数量减少
            Scnt[s.charAt(i+size)-'a']++; // 窗口右侧对应的字符数量增加
            
            // 判断字符组成是否完全相同
            if(Arrays.equals(Scnt,Pcnt)) {
                res.add(i+1);
            }
        }

        return res;
    }
}

---

10、和为K的子数组

求解思路： 暴力两层循环直接过了，不懂
【暴力法】

java">class Solution {
    public int subarraySum(int[] nums, int k) {
        int res = 0;
        int n = nums.length;
        // 左边界
        for(int i=0;i<n;i++) { 
            int sum = nums[i];
            // 不要漏
            if(sum == k) {
                res += 1;
                // continue;    这个是错误的，虽然已经相等了，但是不能忘记后面可能会有+0的情况
            }
            
            // 右边界
            for(int j=i+1;j<n;j++) {
                sum += nums[j];
                if(sum == k) {
                    res += 1;
                    // break; 这个是错误的，虽然已经相等了，但是后面可能还有 +0 或 正负和为0
                }
            }
        }
        return res;
    }
}

---

11、总结

今天的题目对于我这个小菜鸡来说还是有点难度的。不过每一题都给我学到了一些东西。总体上涉及到哈希表的常用方法和场景、Arrays工具类、动态规划、双指针、滑动窗口等知识点。过两天需要复习巩固！