1、两数之和

在数组中找到两个整数之和为target的整数，返回这两个整数的下标。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1]

思路：利用python中的字典，将元素存为key，下标存为value。遍历数组，判断target-nums[i]是否在dict键中，有的话，将value和当前 i 存入列表并返回；没有的话，将当前 i 和nums[i] 存入字典

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
       map_tmp = {}
       res = []
       for idx, num in enumerate(nums):
        if target - num in map_tmp:
            res.append(map_tmp[target - num])
            res.append(idx)
            return res
        else:
            map_tmp[num] = idx
                
        

2、字母异位词分组

将一个字符串数组里面的异位词组合在一起返回。

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]

输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

思路：使用python的dict，将排好序的字符串作为dict的key，将当前元素作为dict的value，其中value是列表类型。第一次需要将这个列表创建出来。然后遍历dict，将value返回即可。

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        dict_tmp = {}
        for s in strs:
            key = str(sorted(s))
            if key not in dict_tmp:
                dict_tmp[key] = []
            dict_tmp[key].append(s)

        res = []
        for key in dict_tmp:
            res.append(dict_tmp[key])
        return res

        

3、最长连续序列

找到数组中的最长连续序列，用O(n)解决

示例 1：

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

思路：返回最长长度就是找到一个最长的序列，那需要找到这个序列的最小值和最大值，然后相减就可以。遍历数组，判断当前元素是否为连续序列的最小值。如果小1值存在，证明当前元素是连续序列中的一部分，但不是最小的，需要下一轮循环接着判断。如果大1值存在，需要不断循环判断更大的是否存在，知道序列的最大值。

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        nums = set(nums)
        res = 1
        if len(nums) == 0:
            return 0
        for x in nums:

            if x - 1 in nums:
                continue
            y = x + 1 
            while y in nums:
                y += 1
            res = max(res,y - x)
        return res

                
        

4、移动零

将数组中的0元素都移动到末尾，其他元素顺序不变。

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

思路：遍历数组，遇到0，就利用python的pop()。但是要注意的问题是pop()函数一旦使用数组就会发生变化，所以遍历数组的下标就会改变，所以需要从末尾到头这样遍历数组。

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        cnt = 0
        for i in range(len(nums)-1,-1,-1):
            if nums[i] == 0:
                nums.pop(i)
                cnt += 1
        for i in range(cnt):
            nums.append(0)

5、盛最多水的容器

有一个height数组表示高度，容器就是两个高度和x轴组成的面积，想要面积最大。

示例 1：

输入：[1,8,6,2,5,4,8,3,7]
输出：49 

思路：想要找最大面积，先考虑底部的距离最大，所以使用双指针，根据两侧数值的大小，不断维护最大值。

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

6、三数之和

给一个整数数组，判断其中是否存在nums[i] + nums[j] + nums[k] = 0，其中i j k的下标不一样，并且最后和为0的三元组不重复。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

思路：这里的一个主要问题就是不重复，所以先排序，然后利用双指针，将重复的跳过去。遍历数组，如果存在重复的直接跳到最后一个不重复的位置。l指针是当前元素的下一个，r指针是数组的最后一个元素。首先判断特殊情况，一个是数组个数是否<3，另一个是当前元素是否>0。特殊情况判断完成之后，看当前元素和 l 位置元素 r 位置元素的和是否为0，是0的话直接将结果更新，并将 l r 重复的跳过，并更新 l r 的位置。不是的话，判断是否<0 小于0 证明 l 太小，可右移；否则r 左移。

class Solution:
    def threeSum(self, nums: list[int]) -> list[list[int]]:
        nums = sorted(nums)
        res = []
        for i in range(len(nums)):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            if nums[i] > 0:
                break
            l = i + 1
            r = len(nums) - 1
            
            while l < r:
                if nums[i] + nums[l] + nums[r] == 0:
                    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
                elif nums[i] + nums[l] + nums[r] < 0:
                    l += 1
                else:
                    r -= 1
            
        return res




        

7、每日一题：1594矩阵最大非负积 

在m*n矩阵中，只能向右或者向下移动，从0，0位置出发一直到右下角的所有路径中，找到最大的非负积，对10^9 + 7取余，如果最大积为负数，返回-1.

示例 1：

输入：grid = [[-1,-2,-3],[-2,-3,-3],[-3,-3,-2]]
输出：-1
解释：从 (0, 0) 到 (2, 2) 的路径中无法得到非负积，所以返回 -1 

思路：动态规划，维护一个dp[i][j][2]的数组，dp[i][j][0]表示该位置的最大值，dp[i][j][1]表示改位置的最小值。该位置只能从上或者左更新而来，所以先初始化最左侧一列和最上面一列。然后更新每个位置的取值。之所以保留每个位置的最大和最小值是因为有负数的存在。最后返回右下角的最大值。

class Solution:
    def maxProductPath(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        mod = 10 ** 9 + 7
        dp = [[[0.0,0.0] for _ in range(n)] for _ in range(m)]
        dp[0][0][0] = dp[0][0][1] = grid[0][0]
        for i in range(1,m):
            tmp = dp[i - 1][0][0] * grid[i][0]
            dp[i][0][0] = dp[i][0][1] = tmp
        for i in range(1,n):
            tmp = dp[0][i - 1][0] * grid[0][i]
            dp[0][i][0] = dp[0][i][1] = tmp
        for i in range(1,m):
            for j in range(1,n):
                tmp = [
                    dp[i-1][j][0] * grid[i][j], dp[i][j-1][0] * grid[i][j],
                    dp[i-1][j][1] * grid[i][j], dp[i][j-1][1] * grid[i][j]
                ]
                dp[i][j][0] = max(tmp)
                dp[i][j][1] = min(tmp)

        res = dp[m-1][n-1][0]
        if res < 0:
            return -1
        else:
            return int(res % mod)