数组 & 哈希

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)

---

2. 字母异位词分组

难度：中等 | 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)

---

3. 最长连续序列

难度：中等 | 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)

分析	说明
时间	for循环和while是相加的->2n (只有头节点进入了内循环)

---

总结

题目	核心技巧	时间	空间
两数之和	哈希表查找补数	O(n)	O(n)
字母异位词分组	排序后作为 key	O(nk log k)	O(nk)
最长连续序列	HashSet + 起点判断	O(n)	O(n)