哈希计数与关系建模

def group_anagrams(words: list[str]) -> list[list[str]]:
    """Words grouped by anagram class, groups in order of first appearance."""
    index: dict[str, int] = {}  # canonical key -> position of its group
    groups: list[list[str]] = []
    for w in words:
        key = "".join(sorted(w))  # anagrams share their sorted letters
        if key not in index:
            index[key] = len(groups)
            groups.append([])
        groups[index[key]].append(w)
    return groups

// Words grouped by anagram class, groups in order of first appearance.
vector<vector<string>> groupAnagrams(const vector<string>& words) {
    unordered_map<string, int> index;  // canonical key -> position of its group
    vector<vector<string>> groups;
    for (const string& w : words) {
        string key = w;
        sort(key.begin(), key.end());  // anagrams share their sorted letters
        auto [it, fresh] = index.try_emplace(key, (int)groups.size());
        if (fresh) groups.emplace_back();
        groups[it->second].push_back(w);
    }
    return groups;
}

class Solution {
    // Words grouped by anagram class, groups in order of first appearance.
    List<List<String>> groupAnagrams(String[] words) {
        Map<String, List<String>> groups = new LinkedHashMap<>(); // canonical key -> its words, in first-seen order
        for (String w : words) {
            char[] letters = w.toCharArray();
            Arrays.sort(letters); // anagrams share their sorted letters
            groups.computeIfAbsent(new String(letters), k -> new ArrayList<>()).add(w);
        }
        return new ArrayList<>(groups.values());
    }
}

import "sort"

// groupAnagrams returns the words grouped by anagram class, in order of first appearance.
func groupAnagrams(words []string) [][]string {
	index := map[string]int{} // canonical key -> position of its group
	var groups [][]string
	for _, w := range words {
		letters := []byte(w)
		sort.Slice(letters, func(i, j int) bool { return letters[i] < letters[j] })
		key := string(letters) // anagrams share their sorted letters
		at, ok := index[key]
		if !ok {
			at = len(groups)
			index[key] = at
			groups = append(groups, nil)
		}
		groups[at] = append(groups[at], w)
	}
	return groups
}

def longest_consecutive(nums: list[int]) -> int:
    """Length of the longest run of consecutive integers, in O(n)."""
    have = set(nums)
    best = 0
    for x in have:
        if x - 1 in have:
            continue  # not a run start: the run is counted from its start
        y = x
        while y + 1 in have:
            y += 1
        best = max(best, y - x + 1)
    return best

// Length of the longest run of consecutive integers, in O(n).
int longestConsecutive(const vector<int>& nums) {
    unordered_set<int> have(nums.begin(), nums.end());
    int best = 0;
    for (int x : have) {
        if (have.count(x - 1)) continue;  // not a run start: the run is counted from its start
        int y = x;
        while (have.count(y + 1)) y++;
        best = max(best, y - x + 1);
    }
    return best;
}

class Solution {
    // Length of the longest run of consecutive integers, in O(n).
    int longestConsecutive(int[] nums) {
        Set<Integer> have = new HashSet<>();
        for (int x : nums) have.add(x);
        int best = 0;
        for (int x : have) {
            if (have.contains(x - 1)) continue; // not a run start: the run is counted from its start
            int y = x;
            while (have.contains(y + 1)) y++;
            best = Math.max(best, y - x + 1);
        }
        return best;
    }
}

// longestConsecutive returns the length of the longest run of consecutive integers, in O(n).
func longestConsecutive(nums []int) int {
	have := map[int]bool{}
	for _, x := range nums {
		have[x] = true
	}
	best := 0
	for x := range have {
		if have[x-1] {
			continue // not a run start: the run is counted from its start
		}
		y := x
		for have[y+1] {
			y++
		}
		best = max(best, y-x+1)
	}
	return best
}