LeetCode:数组（二）

本组囊括数组相关题目，难度不等：

35.Search Insert Position

题目描述：简单

这是一个简单的二分查找问题，只不过最后寻找完后未找到就返回Low而不是None，这里即可返回目标值应插入位置，注意：这里的重点在于二分法的边界条件不要弄错，记住这个模板。

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        low = 0 
        high = len(nums) - 1
        while low <= high:
            mid = (high + low) // 2
            guess = nums[mid]

            if guess == target:
                return mid
            elif guess > target:
                high = mid - 1
            else:
                low = mid + 1
        return low
        # 二分查找的模板，要记住边界条件

41.First Missing Positive

题目描述：困难

提示：

你的算法的时间复杂度应为O(n)，并且只能使用常数级别的额外空间。

如果没有这条提示，其实最暴力解法是先做快速排序，再做二分查找，但这样时间复杂度太高了。

解法一：

## 官方正解：将数组视为哈希表，自己重写编写哈希函数的规则
## 就这个题目来说，规则即把数组中值为i的数映射到下标i-1去，如把数字1放到a[0]：

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        # 自己想到的是先做快速排序，再做二分查找，这样不符合时间复杂度
        ## 正解：讲数组视为哈希表，自己重写编写哈希函数的规则
        ## 就这个题目来说，规则即把数组中值为i的数映射到下标i-1去，如把数字1放到a[o]：
        size = len(nums)
        for i in range(size):
            # 首先判断这个i是新数组的索引对应的值， 不满足条件就交换
            while 1 <= nums[i] <= len(nums) and nums[i] != nums[nums[i]-1]:
                self.__swap(nums, i, nums[i]-1)
        
        for i in range(size):
            if i+1 != nums[i]:
                return i+1  # 这里遍历一遍新数组，如果当前下标对应的值不是下标+1的话，就返回下标+1即为答案
        return size+1 # 遍历完仍没出现上述情况，则整个新数组长度+1即为正确答案
    # 这里记住一点，次要逻辑都可以重新写一个函数，这样可以避免出错
    def __swap(self, nums, index1, index2):
        nums[index1], nums[index2] = nums[index2], nums[index1]

53.Maximum Subarray

题目描述：简单

这道题求的是最大子序和，通常解法是由动态规划的思路求解，但题目中进阶所说的使用分治法求解较为困难，这里先不使用。

回到动态规划：我们可以考虑设置一个sum为数组前几项的和，如果这个和为正，则它对下一个数字有增益，则sum+=当前数字；如果这个和为负，则没有增益，最大和就直接从当前数字开始。遍历数组即可得到最大子序列和。此外，还要用一个ans来保存历史最大子序和的值。

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
    # 参考解法，动态规划
        sum = 0
        ans = nums[0]
        for i in range(len(nums)):
            if sum > 0:
                sum += nums[i]
            else:
                sum = nums[i]
            
            ans = max(ans, sum)
        return ans
        # 时间复杂度 O(n)
        # 空间复杂度 O(1)