class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # 利用hash表，O(n)时间复杂度，O(n)空间复杂度
        d = {}
        for i, n in enumerate(nums):
            m = target - n
            if m in d:
                return [d[m], i]
            else:
                d[n] = i

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()
        for i in range(len(nums)-2):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            l, r = i+1, len(nums)-1
            while l < r:
                s = nums[i] + nums[l] + nums[r]
                if s < 0:
                    l += 1
                elif s > 0:
                    r -= 1
                else:
                    res.append((nums[i], nums[l], nums[r]))
                    while l < r and nums[l] == nums[l+1]:  # 跳过相等的元素
                        l += 1
                    while l < r and nums[r] == nums[r-1]:
                        r -= 1
                    l += 1
                    r -= 1
        return res

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        def findNsum(l, r, target, N, result, results):
            # early termination
            if r-l+1 < N or N < 2 or target < nums[l]*N or target > nums[r]*N:
                return
            if N == 2:  # two pointers solve sorted 2-sum problem
                while l < r:
                    s = nums[l] + nums[r]
                    if s == target:
                        results.append(result + [nums[l], nums[r]])
                        l += 1
                        while l < r and nums[l] == nums[l-1]:
                            l += 1
                    elif s < target:
                        l += 1
                    else:
                        r -= 1
            else:  # recursively reduce N
                for i in range(l, r+1):
                    if i == l or (i > l and nums[i-1] != nums[i]):
                        findNsum(i+1, r, target-nums[i],
                                 N-1, result+[nums[i]], results)

        nums.sort()
        results = []
        findNsum(0, len(nums)-1, target, 4, [], results)
        return results

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:

        qian_zhui = []  # 前缀乘积，qian_zhui[i]表示nums[:i]的累积
        s = 1
        for i in range(len(nums)):
            qian_zhui.append(s)
            s *= nums[i]

        hou_zhui = []  # hou_zhui[i]表示nums[i+1:]的累积
        s = 1
        for x in reversed(nums):
            hou_zhui.append(s)
            s *= x
        hou_zhui.reverse()
        return [x*y for x, y in zip(qian_zhui, hou_zhui)]

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if not nums:
            return 0

        i = 0
        for j in range(1, len(nums)):
            if nums[j] != nums[i]:
                i += 1
                nums[i] = nums[j]
        return i+1

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        i = 0
        for n in nums:
            if i < 2 or n > nums[i-2]:
                nums[i] = n
                i += 1
        return i

class Solution:
    def maxArea(self, height: List[int]) -> int:
        i, j, res = 0, len(height)-1, 0
        while i < j:
            if height[i] >= height[j]:
                res = max(res, height[j]*(j-i))
                j -= 1
            elif height[i] < height[j]:
                res = max(res, height[i]*(j-i))
                i += 1
        return res

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        res = []
        while matrix:
            res += matrix.pop(0)
            matrix = list(map(list, zip(*matrix)))[::-1]
        return res

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        p1 = m - 1
        p2 = n - 1
        # set pointer for nums1
        p = m + n - 1

        # while there are still elements to compare
        while p1 >= 0 and p2 >= 0:
            if nums1[p1] < nums2[p2]:
                nums1[p] = nums2[p2]
                p2 -= 1
            else:
                nums1[p] = nums1[p1]
                p1 -= 1
            p -= 1

        # add missing elements from nums2
        nums1[:p2 + 1] = nums2[:p2 + 1]

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0
        left_max = [0]*len(height)
        right_max = [0]*len(height)

        left_max[0] = height[0]
        for i in range(1, len(height)):
            left_max[i] = max(height[i], left_max[i-1])

        right_max[-1] = height[-1]
        for i in range(len(height)-2, -1, -1):
            right_max[i] = max(height[i], right_max[i+1])

        res = 0
        for l, r, h in zip(left_max, right_max, height):
            res += (min(l, r) - h)
        return res

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        # 如果序列中没有0存在，那么乘积最大子序列必定是从开头开始的  或者终点在数组末尾
        nums_reversed = nums[::-1]
        for i in range(1, len(nums)):
            nums[i] *= nums[i-1] or 1
            nums_reversed[i] *= nums_reversed[i-1] or 1
        return max(nums+nums_reversed)

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        nums.sort()
        mid = len(nums)//2
        return nums[mid]

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # 进行k次旋转
        # n = len(nums)
        # k %= n
        # for _ in range(k):
        #     nums.insert(0, nums.pop())

        n = len(nums)
        k %= n
        self.reverse(nums, 0, n-1)
        self.reverse(nums, 0, k-1)
        self.reverse(nums, k, n-1)

    def reverse(self, nums, start, end):
        while start < end:
            nums[start], nums[end] = nums[end], nums[start]
            start += 1
            end -= 1

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        first = second = float('inf')
        for n in nums:
            if n <= first:
                first = n
            elif n <= second:
                second = n
            else:
                return True
        return False

import heapq


class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:

        # 1.直接排序 O(NlogN)
        # return sorted(nums, reverse=True)[k-1]

        # 2.1利用堆  O(nlogk)
        # 创建一个大顶堆，遍历所有的元素，在保持堆的大小为k
        # 的情况下尝试将遍历的元素加入堆中
        # 最后堆顶的元素就是正确答案。
        # return heapq.nlargest(k, nums)[-1]

        # 2.2不利用nlargest这个函数的话
        # max_heap = nums[:k]
        # heapq.heapify(max_heap)  # 这个操作O(k)
        # for num in nums[k:]:  # 这个操作是 O((n-k)*logk)
        #     if num > max_heap[0]:  # 大于最大堆中的最小元素
        #         heapq.heappop(max_heap)
        #         heapq.heappush(max_heap, num)
        # return max_heap[0]

        # 2.3还可以对全体元素建堆
        # nums = [-num for num in nums]
        # heapq.heapify(nums)  # O(n)
        # res = None
        # for _ in range(k):  # O(k*logn)
        #     res = heapq.heappop(nums)
        # return -res

        # 3.1递归，利用快排的思想，平均情况下为O(n),
        # 平均情况就是每次取的val刚好能把数列分为两半
        # 最坏的情况下要达到 O(n^2)
        # if k == 1:
        #     return max(nums)

        # partion操作
        # val = nums[0]
        # less, bigger = [], []
        # for n in nums[1:]:
        #     if n >= val:
        #         bigger.append(n)
        #     else:
        #         less.append(n)

        # m = len(bigger)
        # if m == (k-1):
        #     return val
        # elif m > (k-1):
        #     return self.findKthLargest(bigger, k)
        # else:
        #     return self.findKthLargest(less, k-m-1)

        # 3.2 直接在nums在操作，不使用额外的空间
        pos = self.partition(nums, 0, len(nums)-1)
        if pos > len(nums) - k:
            return self.findKthLargest(nums[:pos], k-(len(nums)-pos))
        elif pos < len(nums) - k:
            return self.findKthLargest(nums[pos+1:], k)
        else:
            return nums[pos]

    def partition(self, nums, left, right):
        pivot = left
        for i in range(left, right+1):
            if nums[i] < nums[left]:
                pivot += 1
                nums[i], nums[pivot] = nums[pivot], nums[i]
        nums[left], nums[pivot] = nums[pivot], nums[left]
        return pivot

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        used = {}  # 保存字符到其索引的映射
        max_length = start = 0
        for i, c in enumerate(s):
            if c in used and start <= used[c]:
                start = used[c] + 1
            else:
                max_length = max(max_length, i - start + 1)

            used[c] = i
        return max_length

import collections
class Solution:
    def firstUniqChar(self, s: str) -> int:

        count = collections.Counter(s)
        # find the index
        for i, ch in enumerate(s):
            if count[ch] == 1:
                return i
        return -1

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        res = ""
        for chars in zip(*strs):
            if len(set(chars)) == 1:
                res += chars[0]
            else:
                break
        return res

from collections import Counter
class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        c1 = Counter(s1)
        for i in range(len(s2)-len(s1)+1):
            c2 = Counter(s2[i:i+len(s1)])
            if c1 == c2:
                return True
        return False

class Solution:
    def addStrings(self, num1: str, num2: str) -> str:
        res = ""
        i, j, carry = len(num1) - 1, len(num2) - 1, 0
        while i >= 0 or j >= 0:
            n1 = int(num1[i]) if i >= 0 else 0
            n2 = int(num2[j]) if j >= 0 else 0
            tmp = n1 + n2 + carry
            carry = tmp // 10
            res = str(tmp % 10) + res
            i, j = i - 1, j - 1
        return "1" + res if carry else res

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        res = [0] * (len(num1) + len(num2))
        for i, e1 in enumerate(reversed(num1)):
            for j, e2 in enumerate(reversed(num2)):
                res[i+j] += int(e1) * int(e2)
                res[i+j+1] += res[i+j]//10
                res[i+j] %= 10

        while len(res) > 1 and res[-1] == 0:
            res.pop()
        return ''.join(map(str, res[::-1]))

class Solution:
    def simplifyPath(self, path: str) -> str:
        stack = []
        path = path.split("/")
        for item in path:
            if item == "..":
                if stack:
                    stack.pop()
            elif item and item != ".":
                stack.append(item)
        return "/" + "/".join(stack)

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        res = []
        self.helper(s, 0, "", res)
        return res

    def helper(self, s, index, path, res):
        if index == 4:
            if not s:
                res.append(path[:-1])
            return
        for i in range(1, 4):
            if i <= len(s):
                if int(s[:i]) < 256:
                    self.helper(s[i:], index+1, path+s[:i]+'.', res)
                if s[0] == '0':
                    break