算法 2（哈希表、字符串、双指针总结、栈与队列）

// 场景：统计小写字母频次
int[] count = new int[26]; // 空间极小
for (char c : s.toCharArray()) {
    count[c - 'a']++; // 直接映射，无哈希函数
}

import java.util.HashSet;
import java.util.Set;
import java.util.Iterator;

public class HashSetDemo {
    public static void main(String[] args) {
        /* 1. 初始化哈希集合 */
        // 注意：泛型只填一个类型，即元素的类型
        Set<Integer> set = new HashSet<>();

        /* 2. 添加操作 (对应 HashMap 的 put) */
        // 在集合中添加元素
        // 返回值 boolean: 如果元素原本不存在则添加成功返回 true，如果已存在则返回 false
        set.add(12836);
        set.add(15937);
        set.add(16750);
        set.add(13276);
        set.add(10583);

        /* 3. 查询操作 (对应 HashMap 的 get/containsKey) */
        // HashSet 没有 get(key) 方法，因为存了 key 也就等于存了 value（它俩是一样的）
        // 只能判断元素是否存在
        boolean exists = set.contains(15937);
        System.out.println("15937 是否存在: " + exists);

        /* 4. 删除操作 (对应 HashMap 的 remove) */
        // 删除指定元素
        // 返回值 boolean: 删除成功返回 true，元素不存在返回 false
        set.remove(10583);

        /* 5. 遍历操作 */
        // 方式 A: 增强 for 循环 (最常用，直接遍历元素)
        System.out.println("--- 增强 for 循环 ---");
        for (int num : set) {
            System.out.println(num);
        }

        // 方式 B: 迭代器 Iterator
        System.out.println("--- 迭代器 ---");
        Iterator<Integer> it = set.iterator();
        while(it.hasNext()){
            System.out.println(it.next());
        }

        // 方式 C: forEach (Java 8+)
        System.out.println("--- forEach ---");
        set.forEach(System.out::println);

        // 注意：HashSet 没有 keySet(), values(), entrySet() 这种区分键值的遍历，
        // 因为它本质上就是一个全是 Key 的集合。
        // 但如果你非要转成 Map 看底层，可以强转，但通常不需要。
    }
}

/* 初始化哈希表 */
Map<Integer, String> map = new HashMap<>();

/* 添加操作 */
// 在哈希表中添加键值对 (key, value)
map.put(12836, "小哈");
map.put(15937, "小啰");
map.put(16750, "小算");
map.put(13276, "小法");
map.put(10583, "小鸭");

/* 查询操作 */
boolean bool = map.containsKey(12836);
String name = map.get(15937);
String name = map.getOrDefault(10000,"无");

/* 删除操作 */
// 在哈希表中删除键值对 (key, value)
map.remove(10583);

/* 遍历哈希表 */
// 遍历键值对 key->value
for (Map.Entry <Integer, String> kv: map.entrySet()) {
    System.out.println(kv.getKey() + " -> " + kv.getValue());
}
// 单独遍历键 key
for (int key: map.keySet()) {
    System.out.println(key);
}
// 单独遍历值 value
for (String val: map.values()) {
    System.out.println(val);
}

// 可以把不可变类型作为 key
Map<String, AnyOtherType> map1 = new HashMap<>();
Map<Integer, AnyOtherType> map2 = new HashMap<>();

// 不应该把可变类型作为 key
// 注意，这样写并不会产生语法错误，但是代码非常容易出 bug
Map<ArrayList<Integer>, AnyOtherType> map3 = new HashMap<>();

public class Test {
    public static void main(String[] args) {
        // 错误示例
        // 把可变类型作为 HashMap 的 key
        Map<ArrayList<Integer>, Integer> map = new HashMap<>();

        ArrayList<Integer> arr = new ArrayList<>();
        arr.add(1);
        arr.add(2);

        map.put(arr, 999);
        System.out.println(map.containsKey(arr)); // true
        System.out.println(map.get(arr)); // 999

        arr.add(3);
        // 出现严重 bug，键值对丢失
        System.out.println(map.containsKey(arr)); // false
        System.out.println(map.get(arr)); // null

        // 此时 map 底层的 table 中，arr 的键值对数据依然存在
        // 但是由于 arr 的 hashCode 改变了，此键值对无法被查找到
        // 这也会导致内存泄漏，因为这个 arr 变量被 map 引用着，无法被垃圾回收
    }
}

class Solution {
    public boolean isAnagram(String s, String t) {
        int[] record = new int[26];

        for (int i = 0; i < s.length(); i++) {
            record[s.charAt(i) - 'a']++;     // 并不需要记住字符a的ASCII，只要求出一个相对数值就可以了
// String.charAt()返回字符串中指定索引处的 char 值
        }

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

        for (int count: record) {
            if (count != 0) {               // record数组如果有的元素不为零0，说明字符串s和t 一定是谁多了字符或者谁少了字符。
                return false;
            }
        }
        return true;                        // record数组所有元素都为零0，说明字符串s和t是字母异位词
    }
}

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        // 定义一个哈希映射数组
        int[] record = new int[26];

        // 遍历
        for(char c : magazine.toCharArray()){
            record[c - 'a'] += 1;
        }

        for(char c : ransomNote.toCharArray()){
            record[c - 'a'] -= 1;
        }

        // 如果数组中存在负数，说明ransomNote字符串中存在magazine中没有的字符
        for(int i : record){
            if(i < 0){
                return false;
            }
        }

        return true;
    }
}

// 时间复杂度O(n+m+k) 空间复杂度O(n+k)
// 其中n是数组nums1的长度，m是数组nums2的长度，k是交集元素的个数
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> resSet = new HashSet<>();
        //遍历数组1
        for (int i : nums1) {
            set1.add(i);
        }
        //遍历数组2的过程中判断哈希表中是否存在该元素
        for (int i : nums2) {
            if (set1.contains(i)) {
                resSet.add(i);
            }
        }

        //方法1：将结果集合转为数组
        return res.stream().mapToInt(Integer::intValue).toArray();
        /**
         * 将 Set<Integer> 转换为 int[] 数组：
         * 1. stream() : Collection 接口的方法，将集合转换为 Stream<Integer>
         * 2. mapToInt(Integer::intValue) :
         *    - 中间操作，将 Stream<Integer> 转换为 IntStream
         *    - 使用方法引用 Integer::intValue，将 Integer 对象拆箱为 int 基本类型
         * 3. toArray() : 终端操作，将 IntStream 转换为 int[] 数组。
         */

        //方法2：另外申请一个数组存放setRes中的元素,最后返回数组
        int[] arr = new int[resSet.size()];
        int j = 0;
        for(int i : resSet){
            arr[j++] = i;
        }

        return arr;
    }
}

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        int[] hash1 = new int[1002];
        Set<Integer> resSet = new HashSet<>();
        for(int i : nums1){
            hash1[i] = 1;
        }
        for(int i : nums2){
            if(hash1[i] == 1){
                resSet.add(i);
            }
        }

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

class Solution {
    public boolean isHappy(int n) {
        Set<Integer> record = new HashSet<Integer>();
        // n 变为 1 或者 n 循环到之前出现的数值时跳出循环
        while(n != 1&& !record.contains(n)){
            record.add(n);
            n = next(n);
        }
        if(n==1) return true;
        else return false;
    }

    private int next(int n){
        int res = 0;
        while(n!=0){
            int temp = n % 10;
            res += temp * temp;
            n/=10;
        }
        return res;
    }
}

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> num_set = new HashSet<>();
        int longestLen = 0;
        for (int num : nums) num_set.add(num);
        for (int num : num_set) {
            if (!num_set.contains(num - 1)) {
                int currentNum = num;
                int currentLen = 1;
                while (num_set.contains(currentNum + 1)) {
                    currentNum += 1;
                    currentLen += 1;
                }
                longestLen = Math.max(longestLen, currentLen);
            }
        }
        return longestLen;
    }
}

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        // 创建哈希表：Key为排序后的字符串（特征值），Value为原始字符串列表
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            // 1. 将字符串转为字符数组并排序，作为区分异位词的“唯一键”
            char[] array = str.toCharArray();
            Arrays.sort(array);
            String key = new String(array);

            // 2. 获取该键对应的列表，若不存在则创建新列表
            List<String> list = map.getOrDefault(key, new ArrayList<>());

            // 3. 将原始字符串加入列表，并更新回地图（注意：list是引用，其实可省略put，但写上更直观）
            list.add(str);
            map.put(key, list);
        }
        // 返回地图中所有的值（即分组后的列表集合）
        return new ArrayList<>(map.values());
        // map.values() 返回的类型是 Collection<List<String>>
        // 构造函数签名是 public ArrayList(Collection<? extends E> c)
    }
}

class LRUCache {
    private final int capacity;
    private final Map<Integer, Integer> cache = new LinkedHashMap<>(); // 内置 LRU

    public LRUCache(int capacity) {
        this.capacity = capacity;
    }

    public int get(int key) {
        // 删除 key，并利用返回值判断 key 是否在 cache 中
        Integer value = cache.remove(key);
        if (value != null) { // key 在 cache 中
            cache.put(key, value);
            return value;
        }
        // key 不在 cache 中
        return -1;
    }

    public void put(int key, int value) {
        // 删除 key，并利用返回值判断 key 是否在 cache 中
        if (cache.remove(key) != null) { // key 在 cache 中
            cache.put(key, value);
            return;
        }
        // key 不在 cache 中，那么就把 key 插入 cache，插入前判断 cache 是否满了
        if (cache.size() == capacity) { // cache 满了
            Integer eldestKey = cache.keySet().iterator().next();
            cache.remove(eldestKey); // 移除最久未使用 key
        }
        cache.put(key, value);
    }
}

public int[] twoSum(int[] nums, int target) {
    Map<Integer,Integer> recordMap = new HashMap<>();
    // 遍历数组
    for(int i=0;i<nums.length;i++){
        int complement = target-nums[i];
        // 1、查之前存入的 map 中是否有匹配值
        if(recordMap.containsKey(complement)) return new int[]{recordMap.get(complement), i}; // 返回两个数的下标
        // 2、把当前数值和下标存入 map
        recordMap.put(nums[i],i);
    }
    return null;
}

List<int[]> result = new ArrayList<>();
// Key: 数值, Value: 该数值出现过的所有索引列表
Map<Integer, List<Integer>> map = new HashMap<>();

// 遍历数组
for (int i = 0; i < nums.length; i++) {
    int num = nums[i];
    int complement = target - num;

    // 1、查之前存入的 map 中是否有匹配值
    if (map.containsKey(complement)) {
        // 获取互补值之前出现的所有索引
        List<Integer> prevIndices = map.get(complement);

        // 遍历这些索引，与当前的 i 组成所有可能的对
        for (int prevIndex : prevIndices) {
            // 因为 prevIndex 肯定小于 i (它是之前的)，所以天然满足不重复、不自指
            result.add(new int[]{prevIndex, i});
        }
    }

    // 2、把当前数字和它的索引存入 Map
    // 如果 Key 不存在，先创建一个新列表
    map.putIfAbsent(num, new ArrayList<>());
    // 将当前索引加入列表
    map.get(num).add(i);
}

return result;

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        int res = 0;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        // 1、遍历 A+B 统计两个数组中的元素之和，同时统计出现的次数，放入map
        for (int i : nums1) {
            for (int j : nums2) {
                int sum = i + j;
                map.put(sum, map.getOrDefault(sum, 0) + 1);
            }
        }
        // 2、遍历 C+D 统计剩余的两个元素的和，在map中找是否存在相加为0的情况，同时记录次数
        for (int i : nums3) {
            for (int j : nums4) {
                res += map.getOrDefault(0 - i - j, 0); // 不能直接用 get 方法，get 会返回 null，基本数据类型int不能直接与null进行加法运算
            }
        }
        return res;
    }
}

// 时间复杂度：O(n^2)
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        // 找出a + b + c = 0
        // a = nums[i], b = nums[left], c = nums[right]
        for (int i = 0; i < nums.length-2; i++) {
            // 剪枝
            // 排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组，直接返回结果就可以了
            if (nums[i] > 0) {
                return result;
            }

            // 去重a
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            int left = i + 1;
            int right = nums.length - 1;
            while (left < right) {// 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]));
                    // 对b和c去重的逻辑放在找到一个三元组之后
                    while (left < right && nums[right] == nums[right - 1]) right--;
                    while (left < right && nums[left] == nums[left + 1]) left++;

                    right--;
                    left++;
                }
            }
        }
        return result;
    }
}

import java.util.*;
public class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);  // 排序数组
        List<List<Integer>> result = new ArrayList<>();  // 结果集
        for (int i = 0; i < nums.length-3; i++) {
            // 剪枝
            if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
                break;
            }
            if ((long) nums[i] + nums[nums.length - 3] + nums[nums.length - 2] + nums[nums.length - 1] < target) {
                continue;
            }
            // 对nums[i]去重
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            for (int j = i + 1; j < nums.length-2; j++) {
                // 剪枝
                if ((long) nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
                    break;
                }
                if ((long) nums[i] + nums[j] + nums[nums.length - 2] + nums[nums.length - 1] < target) {
                    continue;
                }
                // 对nums[j]去重
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                int left = j + 1;
                int right = nums.length - 1;
                while (left < right) {
                    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum > target) right--;
                    else if (sum < target) left++;
                    else {
                        result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        // 对nums[left]和nums[right]去重
                        while (left < right && nums[right] == nums[right - 1]) right--;
                        while (left < right && nums[left] == nums[left + 1]) left++;
                        right--;
                        left++;
                    }
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {1, 0, -1, 0, -2, 2};
        int target = 0;
        List<List<Integer>> results = solution.fourSum(nums, target);
        for (List<Integer> result : results) {
            System.out.println(result);
        }
    }
}

String s = "leetcode";
// 取 "leet" (索引 0 到 3)
String sub = s.substring(0, 4);

// 取从索引 4 到末尾 "code"
String suffix = s.substring(4); // 等价于 substring(4, s.length())

// 寻找第一个空格
int spaceIndex = s.indexOf(' ');
// 从索引 5 开始寻找 "abc"
int idx = s.indexOf("abc", 5);

StringBuilder sb = new StringBuilder();
for (char c : chars) {
    if (Character.isLetter(c)) {
        sb.append(c);
    }
}
return sb.toString();

class Solution {
    private int i = 0;
    public String decodeString(String s) {
        return decode(s.toCharArray());
    }

    private String decode(char[] s) {
        StringBuilder res = new StringBuilder();
        int k = 0;
        while (i < s.length) {
            char c = s[i];
            i++;
            // 【递前的准备工作】
            if (Character.isLetter(c)) res.append(c);
            else if (Character.isDigit(c)) k = k * 10 + (c - '0');
            // 【递】
            else if (c == '[') {
                String t = decode(s); // 递归调用
                // 【归】
                for (int j = 0; j < k; j++) res.append(t); // 把括号内的字符串重复 k 次
                k = 0; // 重置 k，若不重置，2[a]3[b] 后面的 3 会算出 k = 23
            } else // 【边界条件】c == ']'
                break;
        }
        return res.toString();
    }
}

for (int i = 0; i < nums.length; i++) {
    for (int j = i; j < nums.length; j++) {
        // nums[i, j] 是一个子数组
    }
}

// 滑动窗口算法伪码框架
void slidingWindow(String s) {
    // 根据场景用合适的数据结构记录窗口数据
    // 比如说，我想记录窗口中元素出现的次数，就用 map
    // 如果我想记录窗口中的元素和，就可以只用一个 int
    Object window = ...

    // 左闭右开窗口区间，right指向下一个要进来的
    int left = 0, right = 0;

    // 结果数据
    Object result = ...

    while (right < s.length()) {
        // c 是将移入窗口的字符，更新窗口数据
        char c = s[right];
        window.add(c)
        ...

        // 增大窗口
        right++;

        // *** debug 输出的位置 ***
        // 注意在最终的解法代码中不要 print
        // 因为 IO 操作很耗时，可能导致超时
        // printf("window: [%d, %d)\n", left, right);
        // ***********************

        // 判断左侧窗口是否要收缩
        while (left < right && window needs shrink) {
            // d 是将移出窗口的字符，更新窗口数据
            char d = s[left];
            window.remove(d)
            ...

            // 缩小窗口
            left++;
        }
    }
    // 返回结果数据
    return result;
}

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int result = INT32_MAX; // 最终的结果
        int sum = 0; // 子序列的数值之和
        for (int left = 0; left < nums.size(); left++) { // 设置子序列起点为i
            sum = 0;
            for (int right = left; right < nums.size(); right++) { // 设置子序列终止位置为right
                sum += nums[right];
                if (sum >= target) { // 一旦发现子序列和超过了s，更新result
                    result = result < right - left + 1 ? result : right - left + 1;
                    break; // 因为我们是找符合条件最短的子序列，所以一旦符合条件就break
                }
            }
        }
        // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
        return result == INT32_MAX ? 0 : result;
    }
}

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        // 记录窗口数据，这里是元素和sum
        int sum = 0;
        // 窗口区间
        int left = 0, right = 0;
        // 记录结果数据，子数组长度
        int result = Integer.MAX_VALUE;

        while(right < nums.length){
            // nums[right]被移入窗口，进行窗口数据更新
            sum += nums[right];

            // 增大窗口
            right++;

            // 判断左侧窗口是否要收缩
            while(left < right && sum >= target){
                // 更新结果数据
                result = Math.min(result, right-left);

                // nums[left]被移出窗口，进行窗口数据更新
                sum -= nums[left];

                // 缩小窗口
                left++;
            }
        }
        // 返回结果数据，子数组长度
        return result == Integer.MAX_VALUE ? 0 : result;
    }
}

class Solution {
    public String minWindow(String s, String t) {
        Map<Character, Integer> need = new HashMap<>();
        for (char c : t.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }

        // 记录窗口数据
        Map<Character, Integer> window = new HashMap<>();
        int valid = 0; // 窗口中满足 need 条件的字符个数，如果 valid=need.size，则说明窗口已满足条件，完全覆盖了串 T

        // 左闭右开窗口区间
        int left = 0, right = 0;

        // 记录结果数据，最小覆盖子串的起始索引及长度
        int start = 0, len = Integer.MAX_VALUE;

        while (right < s.length()) {
            // c 是将移入窗口的字符，进行窗口数据更新
            char c = s.charAt(right);
            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                if (window.get(c).equals(need.get(c)))
                    valid++;
            }

            // 增大窗口
            right++;

            // 判断左侧窗口是否要收缩
            while (valid == need.size()) {
                // 更新结果数据，最小覆盖子串
                if (right - left < len) {
                    start = left;
                    len = right - left;
                }

                // d 是将移出窗口的字符，更新窗口数据
                char d = s.charAt(left);
                if (need.containsKey(d)) {
                    if (window.get(d).equals(need.get(d)))
                        valid--;
                    window.put(d, window.get(d) - 1);
                }

                // 缩小窗口
                left++;
            }
        }
        // 返回结果数据，最小覆盖子串
        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }
}