class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hash = {}
        
        for i in range(len(nums)):
            cur = target - nums[i]
            if cur in hash:
                return [i,cur]
            hash[nums[i]] = i
        return [-1,-1]

from typing import List
from collections import defaultdict


class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        # 自动创建空列表作为默认值
        hash_map: dict[str, list[str]] = defaultdict(list)
        for s in strs:
            code = self.encode(s)
            hash_map[code].append(s)
        return list(hash_map.values())  # ← 核心修复

    def encode(self, s: str) -> str:
        arr = [0] * 26  # ← 26 而非 27
        for c in s:
            arr[ord(c) - ord("a")] += 1
        return "#".join(str(num) for num in arr)

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        # 1.找出开始位置
        # 2.每次+1尝试访问

        nums_set: set[int] = set(num for num in nums)
        count = 0
        for num in nums_set:
            # 找到开始位置
            if num - 1 in nums_set:
                continue
            cur_count = 0
            while num in nums_set:
                cur_count += 1
                num += 1
            count = max(count, cur_count)
        return count

class *Solution*:
    def *merge*(*self*, *intervals*: *List*[*List*[*int*]]) -> *List*[*List*[*int*]]:
        res = []

        *intervals*.*sort*(*key*=lambda *x*: *x*[*0*])

        *# 先加入第一个为默认范围*
        res.*append*(*intervals*[*0*])

        for i in *range*(1, *len*(*intervals*)):
            cur_arr = *intervals*[*i*]

            *# 获取已经选择的区间*
            last = *res*[-*1*]

            if *cur_arr*[*0*] <= *last*[*1*]:
                *# 说明cur_arr在区间范围内*
                *# 寻找末尾最大值*
                *last*[*1*] = *max*(*last*[*1*], *cur_arr*[*1*])
            else:
                *# 开始进行新的区间*
                res.*append*(cur_arr)
        return res

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        window = 0
        l = r = 0
        max_val = float("-inf")
        while r < len(nums):
            num = nums[r]
            r += 1
            window += num

            max_val = max(window, max_val)

            while window < 0:
                window -= nums[l]
                l += 1
        return max_val

# 要么自成一派，要么和前面的子数组合并
dp[i] = max(nums[i], nums[i] + dp[i - 1])

class *Solution*:
    def *maxSubArray*(*self*, *nums*: *List*[*int*]) -> *int*:
        if *len*(*nums*) == 0:
            return 0
        dp = [0] * *len*(*nums*)

        for i in *range*(*len*(*nums*)):
            *# 作选择*
            *dp*[*i*] = *max*(*nums*[*i*], *nums*[*i*] + *dp*[*i *-* 1*])

        max_val = *float*("-inf")
        for val in dp:
            max_val = *max*(max_val, val)

        return max_val

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        k %= len(nums)
        # 整体反转
        self.reverse(0, len(nums) - 1, nums)
        # 前 k-1 反转
        self.reverse(0, k - 1, nums)
        # 后 [k,n-1]反转
        self.reverse(k, len(nums) - 1, nums)

    def reverse(self, left: int, right: int, nums: list[int]) -> None:
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        # 1.把不符合范围的提前去除
        for i in range(n):
            if nums[i] <= 0 or nums[i] > n:
                nums[i] = n + 1
        # 2.遍历一次，把出现过的位置用负号表示出现过
        for i in range(n):
            x = abs(nums[i])
            # 防止数组越界
            if x <= n:
                # 只是改为负号，并没有覆盖值
                nums[x - 1] = -abs(nums[x - 1])
        # 3.遍历一次，找到没有变成负数的
        for i in range(n):
            if nums[i] > 0:
                return i + 1
        # 1..n 全都出现了，答案是 n+1
        return n + 1