02_数组 & 哈希

🎯 LeetCode Hot 100

---

1. 两数之和

难度：简单 | LeetCode 链接

给定数组 nums 和目标值 target，找出和为目标值的两个数的下标。

输入：nums = [2,7,11,15], target = 9
输出：[0,1]

思路

用哈希表存储已遍历的 值 → 索引，每次查找 target - 当前值 是否存在。

代码

class Solution {
    public int[] twoSum(int[] nums, int target) {
        //hashmap 存放value->index
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = 0;i<nums.length;i++){
            int requireValue = target - nums[i];
            //requireValue如果存在，即找到和为target的两个数
            if(map.containsKey(requireValue)){
                return new int[]{i,map.get(requireValue)};
            }
            map.put(nums[i],i);
        }
        return new int[]{};
    }
}

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

---

49. 字母异位词分组

难度：中等 | LeetCode 链接

给定字符串数组，将字母异位词组合在一起。

输入：["eat","tea","tan","ate","nat","bat"]
输出：[["bat"],["nat","tan"],["ate","eat","tea"]]

思路

将每个字符串排序后作为 key，相同 key 的放入同一组。

代码

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        //使用Map存放，排序好的字符串->原字符串List
        Map<String,List<String>> map = new HashMap<>();

        for(int i=0;i<strs.length;i++){
            char[] strArr = strs[i].toCharArray();
            Arrays.sort(strArr);
            String sortedStr = new String(strArr);
            //如果map包含已排序好字符串add,否则new ArrayList并add
            map.computeIfAbsent(sortedStr,k->new ArrayList<>()).add(strs[i]);
        }
        return new ArrayList<>(map.values());
    }
}

复杂度：时间 O(nk log k)，空间 O(nk)

分析	说明
时间	排序单个字符串 O(k log k)，共 n 个字符串 → O(nk log k)
空间	存储 n 个字符串，平均长度 k → O(nk)

💡 优化：用字母计数代替排序，时间可优化到 O(nk)

---

128. 最长连续序列

难度：中等 | LeetCode 链接

找出数组中最长连续序列的长度，要求 O(n) 时间复杂度。

输入：[100,4,200,1,3,2]
输出：4  // 序列 [1,2,3,4]

思路

用 HashSet 存储所有数字，只从序列起点开始计数。

代码

class Solution {
    int ans = 0;
    public int longestConsecutive(int[] nums) {
        //1.去重
        Set<Integer> set = new HashSet<>();
        for(int i = 0;i<nums.length;i++){
            set.add(nums[i]);
        }
        //2.寻找子串的起点值
        for(Integer x:set){
            //如果有下一个不是起点，跳过
            if(set.contains(x-1)){
                continue;
            }
            int y = x + 1;
            //3.循环计数
            while(set.contains(y)){
                y++;//跳出循环时最后一个y要去掉
            }
            //4.记录最大值,x~y-1 连续数= y-x
            ans = Math.max(ans,y-x);
        }
        return ans;
    }
}

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

---

560. 和为 K 的子数组

难度：中等 | LeetCode 链接

给定一个整数数组 nums 和一个整数 k，请你统计并返回该数组中和为 k 的连续子数组的个数。

输入：nums = [1,1,1], k = 2
输出：2

思路

使用前缀和 + 哈希表统计前缀出现次数。当前前缀和为 sum，若存在 sum - k 的前缀出现过，则说明以当前位置结尾的子数组可满足条件。

代码

class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>();
        //key: if pre[i],pre[j] is the sum of 0~i/0~j
        //want solve: pre[i] - pre[j-1] = k
        //pre[j-1] = pre[i] - k
        //if pre[j-1] exists , means pre[i] - pre[j-1] is k  . j ~ i is the subarray we want
        int sum = 0,count = 0;
        //if sum == k need zero key
        map.put(0,1);
        for(int i=0;i<nums.length;i++){
            sum+= nums[i];
            if(map.containsKey(sum-k)){
                count+=map.get(sum-k);
            }
            //the sum as key , occur times as value
            map.put(sum,map.getOrDefault(sum,0)+1);
        }
        return count;
    }
}

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

---