Hexo

LeetCode-Hot100-哈希

  • ~1.94K 字
  1. 1. 1.两数之和 C++
  2. 2. 49.字母异位词分组 Java
  3. 3. 128. 最长连续序列 Java

1.两数之和 C++

创建一个空哈希表（unordered_map<int, int> idx;），
枚举 j，不要带结束条件，不然会报错没有返回值
在 j 左边找 i ，满足 nums[i] + nums[j] = target，(auto it = idx.find(target - nums[j);)
找到了(it != idx.end())，返回两数下标(用{}括起来)，
nums[j] 和 j 加入哈希表(idx[nums[j]] = j 防止一开始加入导致同一个数用两次)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> idx;
        for (int j = 0; ; j++) {
            auto it = idx.find(target - nums[j]);
            if (it != idx.end()) {
                return {it -> second, j};
            }
            idx[nums[j]] = j;
        }
    }
};

49.字母异位词分组 Java

先建一个hashmap，key是排序后的字符串，value是字符串本身的集合，
将字符串转字符数组后排序，再加入hashmap，computeIfAbsent.add，
返回hashmap的values()

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> m = new HashMap<>();
        for (String s : strs) {
            char[] sortedS = s.toCharArray();
            Arrays.sort(sortedS);
            m.computeIfAbsent(new String(sortedS), _ -> new ArrayList<>()).add(s);
        }
        return new ArrayList<>(m.values());
    }
}

128. 最长连续序列 Java

创建哈希集合Set<Integer> st = new HashSet<>();，
将nums中的数加入st.add()，
遍历哈希集合，
如果 x -1在哈希集合st.contains(x-1)，即x不是序列起点，直接跳过，
x 是序列起点，不断查找下一个数是否在哈希集合中，循环结束后， y-1 是最后一个在哈希集合的数，从 x 到 y-1 一共 y-x 个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> st = new HashSet<>();
        for (int num : nums) {
            st.add(num);
        }
        int ans = 0;
        for (int x : st){
            if (st.contains(x - 1)) continue;
            int y = x + 1;
            while (st.contains(y)) y++;
            ans = Math.max(ans, y - x);
        }
        return ans;
    }
}
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可
, , ,