子序列子数组问题 Leetcode

灰太狼 2022-10-31 10:45 225阅读 0赞

# 子序列 子数组问题 #

## [53. 最大子序和][53.] ##

给定一个整数数组 `nums` ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

**示例 1：**

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
    输出：6
    解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

**解法1:** 贪心法

class Solution:
        def maxSubArray(self, nums: List[int]) -> int:
            max_sum = nums[0]
            cur_sum = 0
            for i in range(0, len(nums)):
                cur_sum += nums[i]
                max_sum = max(max_sum, cur_sum)
                if cur_sum < 0:  # 小于0 再加也会减少
                    cur_sum = 0
    
            return max_sum

**解法2：** 动态规划

class Solution:
        def maxSubArray(self, nums: List[int]) -> int:
            # 动态规划,
            for i in range(1, len(nums)):
                if nums[i-1] > 0: # 大于0 加
                    nums[i] = nums[i] + nums[i-1]
    
            return max(nums)

## [674. 最长连续递增序列][674.] ##

给定一个未经排序的整数数组，找到最长且 **连续递增的子序列**，并返回该序列的长度。

**连续递增的子序列** 可以由两个下标 `l` 和 `r`（`l < r`）确定，如果对于每个 `l <= i < r`，都有 `nums[i] < nums[i + 1]` ，那么子序列 `[nums[l], nums[l + 1], ..., nums[r - 1], nums[r]]` 就是连续递增子序列。

**示例 1：**

输入：nums = [1,3,5,4,7]
    输出：3
    解释：最长连续递增序列是 [1,3,5], 长度为3。
    尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。

**解法1:**

class Solution:
        def findLengthOfLCIS(self, nums: List[int]) -> int:
            # 最长 且 连续递增 子序列
            if not nums:
                return 0
            max_length = 1
            temp = 1 # 计算连续递增子序列个数
            for i in range(1, len(nums)):
                if nums[i] > nums[i-1]:
                    temp += 1
                    max_length = max(max_length, temp)
                else:
                    temp = 1
            return max_length

## [300. 最长递增子序列][300.] \*\* 重点复习 ##

给你一个整数数组 `nums` ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，`[3,6,2,7]` 是数组 `[0,3,1,6,2,2,7]` 的子序列。

**示例 1：**

输入：nums = [10,9,2,5,3,7,101,18]
    输出：4
    解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

**解法1：** 动态规划  O ( n 2 ) O(n^2) O(n2)

class Solution:
        def lengthOfLIS(self, nums: List[int]) -> int:
            # 最长严格递增子序列的长度
            # 子序列 和 子数组是不同的；
            # 动态规划
            nums_len = len(nums)
            dp = [] # dp[i]: 表示 到i时 最长严格递增子序列的长度
            for i in range(nums_len):
                dp.append(1) # 从1开始
                # i 和之前的 每个j 比较，若严格递增，则dp[j]+1 比较 
                for j in range(len(dp)):
                    if nums[j] < nums[i]:
                        dp[i] = max(dp[i], dp[j]+1)
    
            return max(dp)

**解法2：**  O ( n l o g ( n ) ) O(nlog(n)) O(nlog(n))

## [673. 最长递增子序列的个数][673.] \*\* 重点复习 ##

给定一个未排序的整数数组，找到最长递增子序列的个数。

**示例 1:**

输入: [1,3,5,4,7]
    输出: 2
    解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。

**解法1:** 动态规划  O ( n 2 ) O(n^2) O(n2)

class Solution:
        def findNumberOfLIS(self, nums: List[int]) -> int:
            # 个数
            nums_len = len(nums)
            length = []
            counts = [] # 第i结尾时，最长递增序列的个数
            for i in range(nums_len):
                length.append(1)
                counts.append(1)
                for j in range(i):
                    if nums[j] < nums[i]: # i 可以放到j后 构成递增序列
                        if length[i] <= length[j]:  # 或者 length[i] < length[j] + 1:
                            length[i] = length[j]+1
                            counts[i] = counts[j] # 长度个数更新
                        elif length[i] == length[j]+1:
                            # 相等
                            counts[i] += counts[j] # 相加
                        
            max_length = max(length)
            max_count = 0
            for i in range(len(length)):  # 长度最长的 对应count数目之和
                if length[i] == max_length:
                    max_count += counts[i]
    
            return max_count

## [1143. 最长公共子序列][1143.] \*\* 动态规划典型题目 ##

给定两个字符串 `text1` 和 `text2`，返回这两个字符串的最长公共子序列的长度。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。  
例如，"`ace`" 是 “`abcde`” 的子序列，但 “`aec`” 不是 “`abcde`” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列，则返回 0。

**示例 1:**

输入：text1 = "abcde", text2 = "ace" 
    输出：3  
    解释：最长公共子序列是 "ace"，它的长度为 3。

**解法1:** **动态规划重点题**

class Solution:
        def longestCommonSubsequence(self, text1: str, text2: str) -> int:
            # 两个字符串的 最长公共子序列
            # 典型动态规划题目， 面试常考题 重点复习记忆, 和 不同路径题目 很相似，都是 典型动态规划题目
            text1_len = len(text1)
            text2_len = len(text2)
            dp = [[0] * (text2_len+1) for _ in range(text1_len+1)]  
            # dp[i][j]: 表示text1[0...i-1]和text2[0...j-1]的最长公共子序列的长度
            # dp[0][0]: 表示 text1和text2为null时 最长公共子序列 为0；
            # dp[1][1]: 表示text1[0]和text2[0]的 最长公共子序列长度； 
            for i in range(1, text1_len+1): # 注意边界条件
                for j in range(1, text2_len+1):
                    if text1[i-1] == text2[j-1]:
                        dp[i][j] = dp[i-1][j-1] + 1
                    else:  # 递归公式
                        dp[i][j] = max(dp[i][j-1], dp[i-1][j])
           
            return dp[text1_len][text2_len]

## [718. 最长重复子数组][718.] \*\* 动态规划 ##

给两个整数数组 `A` 和 `B` ，返回两个数组中公共的、长度最长的子数组的长度。  
**示例：**

输入：
    A: [1,2,3,2,1]
    B: [3,2,1,4,7]
    输出：3
    解释：
    长度最长的公共子数组是 [3, 2, 1] 。

**解法1:** **动态规划**

class Solution:
        def findLength(self, A: List[int], B: List[int]) -> int:
            # 动态规划
            # 子数组 是 连续的！切记！ 子序列不是连续的！ 连续子序列是连续的！
            A_len = len(A)
            B_len = len(B)
            dp = [[0]*(B_len+1) for _ in range(A_len+1)]
            max_res = 0
            for i in range(1, A_len+1):
                for j in range(1, B_len+1):
                    if A[i-1] == B[j-1]:  # 连续条件的判断呢？ 
                        dp[i][j] = dp[i-1][j-1] + 1
                    else:  # 注意递推条件的改变；
                        dp[i][j] = 0  # 不相等就是 0，【保证连续】
                        # dp[i][j] = max(dp[i][j-1], dp[i-1][j])
                    max_res = max(max_res, dp[i][j])
            # print(dp)
            return max_res

## [724. 寻找数组的中心索引][724.] ##

给你一个整数数组 `nums`，请编写一个能够返回数组 **“中心索引”** 的方法。

数组 **中心索引** 是数组的一个索引，其左侧所有元素相加的和等于右侧所有元素相加的和。

如果数组不存在中心索引，返回 `-1` 。如果数组有多个中心索引，应该返回最靠近左边的那一个。

**注意：** 中心索引可能出现在数组的两端。

**解法1:** 前缀和

class Solution:
        def pivotIndex(self, nums: List[int]) -> int:
            total = sum(nums)
            acc_sum = 0
            for i in range(len(nums)):
                if acc_sum == total - acc_sum - nums[i]:
                    return i
                acc_sum += nums[i]
            return -1

## [560. 和为K的子数组][560. _K] \* ##

给定一个整数数组和一个整数 `k`，你需要找到该数组中和为 `k` 的连续的子数组的个数。

**示例 1:**

输入:nums = [1,1,1], k = 2
    输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。

**说明 :**

*  数组的长度为 \[1, 20,000\]。
 *  数组中元素的范围是 \[-1000, 1000\] ，且整数 k 的范围是 \[-1e7, 1e7\]。

class Solution:
        def subarraySum(self, nums: List[int], k: int) -> int:
            # python 枚举超时
            # 前缀和 + 哈希表 优化
            count = 0
            hashtable = { 0:1} # 前缀和作为key，出现次数为value, 存储前缀和；
            preSum = 0 # 前缀和
            for item in nums:
                preSum += item
                if hashtable.get(preSum-k): # 脑子疼..........
                    count += hashtable.get(preSum-k)
                if preSum not in hashtable:
                    hashtable[preSum] = 1  # 
                else:
                    hashtable[preSum] = hashtable[preSum] + 1
            # print(hashtable)
            return count

## [523. 连续的子数组和][523.] \* 重点复习 ##

给定一个包含 **非负数** 的数组和一个目标 **整数** k，编写一个函数来判断该数组是否含有连续的子数组，其大小至少为 2，且总和为 **k** 的倍数，即总和为 n\*k，其中 n 也是一个**整数**。

**示例 1：**

输入：[23,2,4,6,7], k = 6
    输出：True
    解释：[2,4] 是一个大小为 2 的子数组，并且和为 6。

**示例 2：**

输入：[23,2,6,4,7], k = 6
    输出：True
    解释：[23,2,6,4,7]是大小为 5 的子数组，并且和为 42。

**说明：**

*  数组的长度不会超过 10,000 。
 *  你可以认为所有数字总和在 32 位有符号整数范围内。

**解法1:** 前缀和的 思想  
[详解][Link 1]

class Solution:
        def checkSubarraySum(self, nums: List[int], k: int) -> bool:
            # 连续子数组 其大小 >= 2;
            # n 是一个整数，有可能是负数（k<0）
            hashtable = { 0:-1} # key: 前缀和%k, value: 索引
            preSum = 0
            for index, item in enumerate(nums):
                preSum += item
                if k != 0:
                    preSum = preSum % k  # 重点
                if hashtable.get(preSum) != None: # python 为0 也算 （索引有可能为0）
                    if index - hashtable.get(preSum)> 1:
                        return True
                else:
                    hashtable[preSum] = index
    
            return False

## [974. 和可被 K 整除的子数组][974. _ K] ##

给定一个整数数组 `A`，返回其中元素之和可被 `K` 整除的（连续、非空）子数组的数目。

**示例：**

输入：A = [4,5,0,-2,-3,1], K = 5
    输出：7
    解释：
    有 7 个子数组满足其元素之和可被 K = 5 整除：
    [4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

**提示：**

*  1 <= A.length <= 30000
 *  \-10000 <= A\[i\] <= 10000
 *  2 <= K <= 10000

**解法1:** 前缀和  
**思路：**  
那么每个连续子数组的和 s u m ( i , j ) sum(i,j) sum(i,j)就可以写成$ P\[j\] - P\[i-1\]$, 此时，判断子数组的和能否被  K K K 整除就等价于判断  ( P \[ j \] − P \[ i − 1 \] )   m o d   K = = 0 (P\[j\] - P\[i-1\]) \\bmod K == 0 (P\[j\]−P\[i−1\])modK==0，根据 **同余定理**，只要  P \[ j \]   m o d   K = = P \[ i − 1 \]   m o d   K P\[j\] \\bmod K == P\[i-1\] \\bmod K P\[j\]modK==P\[i−1\]modK，就可以保证上面的等式成立。

class Solution:
        def subarraysDivByK(self, A: List[int], K: int) -> int:
            dicts = { 0:1}
            preSum = 0
            count = 0
            for item in A:
                preSum += item
                if K != 0:
                    preSum = preSum % K  ## 取模
                if dicts.get(preSum) != None:
                    count += dicts[preSum]   ## 统计已有的， 已有的每个和 当前这个 都可以组成满足条件的 子数组；
                    dicts[preSum] += 1
                else:
                    dicts[preSum] = 1
    
            return count

## [1248. 统计「优美子数组」][1248.] ##

给你一个整数数组 `nums` 和一个整数 `k`。

如果某个 **连续** 子数组中恰好有 `k` 个奇数数字，我们就认为这个子数组是「**优美子数组**」。

请返回这个数组中「优美子数组」的数目。

**示例 1：**

输入：nums = [1,1,2,1,1], k = 3
    输出：2
    解释：包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。

**方法1:**

class Solution:
        def numberOfSubarrays(self, nums: List[int], k: int) -> int:
            # 如何统计k个 奇数数字 
            odd_list = { 0:1}
            odd_s = 0 # 类似前缀和 （奇数出现之和）
            count = 0  
            for item in nums:
                if item % 2 != 0: # 奇数
                    odd_s += 1
                if odd_list.get(odd_s - k):
                    count += odd_list.get(odd_s - k)
                # count += odd_list.get(odd_s - k, 0)
                if odd_s not in odd_list:
                    odd_list[odd_s] = 1
                else:
                    odd_list[odd_s] += 1
            
            return count

## [713. 乘积小于K的子数组][713. _K] \*\* 多复习 ##

给定一个**正整数**数组 `nums`。

找出该数组内乘积小于 `k` 的连续的子数组的个数。

**示例 1:**

输入: nums = [10,5,2,6], k = 100
    输出: 8
    解释: 8个乘积小于100的子数组分别为: [10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6]。
    需要注意的是 [10,5,2] 并不是乘积小于100的子数组。

**解法1:** 双指针

class Solution:
        def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
            # 数组内都是正整数
            if k <= 1:
                return 0
            acc = 1
            left = 0
            count = 0
            for right, value in enumerate(nums):
                acc *= value
                while acc >= k:  # 组内都是正整数才满足
                    acc /= nums[left]
                    left += 1
                count += right - left + 1  # 很巧妙
            return count

## [325. 和等于 k 的最长子数组长度][325. _ k] ##

给定一个数组 nums 和一个目标值 k，找到和等于 k 的最长子数组长度。如果不存在任意一个符合要求的子数组，则返回 0。

**注意:**  
nums 数组的总和是一定在 32 位有符号整数范围之内的。

**示例 1:**

输入: nums = [1, -1, 5, -2, 3], k = 3
    输出: 4 
    解释: 子数组 [1, -1, 5, -2] 和等于 3，且长度最长。

**解法1:** 前缀和

class Solution:
        def maxSubArrayLen(self, nums: List[int], k: int) -> int:
            # 记下索引位置吗
            prelist = { 0:-1}
            presum = 0
            max_len = 0
            for index, item in enumerate(nums):
                presum += item
                if prelist.get(presum-k) != None: # 切记必须使用None
                    max_len = max(max_len, index-prelist.get(presum-k))
                if presum not in prelist:
                    prelist[presum] = index
    
            return max_len

## [152. 乘积最大子数组][152.] \* ##

给你一个整数数组 `nums` ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

**示例 1:**

输入: [2,3,-2,4]
    输出: 6
    解释: 子数组 [2,3] 有最大乘积 6。

**解法1:** 动态规划

class Solution:
        def maxProduct(self, nums: List[int]) -> int:
            # 求乘积和求和是 有些不同
            # 动态规划
            if len(nums) <= 0:
                return 0
            # 两个数组 
            minValue = nums[0] # 有最大值 最小值 
            maxValue = nums[0]
            ans = nums[0]
            for i in range(1, len(nums)):
                temp = minValue # 切记 ； 
                minValue = min(minValue*nums[i], nums[i], maxValue*nums[i])
                maxValue = max(temp*nums[i], nums[i], maxValue*nums[i])
                ans = max(ans, maxValue)
            return ans

## [238. 除自身以外数组的乘积][238.] \* ##

给你一个长度为 `n` 的整数数组 `nums`，其中 `n > 1`，返回输出数组 `output` ，其中 `output[i]` 等于 `nums` 中除 `nums[i]` 之外其余各元素的乘积。

**示例:**

输入: [1,2,3,4]
    输出: [24,12,8,6]

**提示：** 题目数据保证数组之中任意元素的全部前缀元素和后缀（甚至是整个数组）的乘积都在 32 位整数范围内。

**说明:** 请不要使用除法，且在 **O(n)** 时间复杂度内完成此题。

进阶：  
你可以在常数空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。）

**解法1:** 左部分\*右部分， 注意边界条件

class Solution:
        def productExceptSelf(self, nums: List[int]) -> List[int]:
            # 两次遍历， 左部分乘积， 右部分乘积；结果：左部分乘积*右部分乘积；
            # 左右两端，都为1
            left = 1
            nums_len = len(nums)
            res = [0]*nums_len
            for i in range(nums_len):
                if i > 0:  # 注意边界条件
                    left = left*nums[i-1]
                res[i] = left
            # 右部分
            right = 1
            for i in range(nums_len-1, -1, -1):
                if i < nums_len-1:
                    right = right*nums[i+1]
                res[i] = res[i]*right  # 注意边界条件
            return res

[53.]: https://leetcode-cn.com/problems/maximum-subarray
[674.]: https://leetcode-cn.com/problems/longest-continuous-increasing-subsequence/
[300.]: https://leetcode-cn.com/problems/longest-increasing-subsequence/
[673.]: https://leetcode-cn.com/problems/number-of-longest-increasing-subsequence/
[1143.]: https://leetcode-cn.com/problems/longest-common-subsequence/
[718.]: https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/
[724.]: https://leetcode-cn.com/problems/find-pivot-index/
[560. _K]: https://leetcode-cn.com/problems/subarray-sum-equals-k/
[523.]: https://leetcode-cn.com/problems/continuous-subarray-sum/
[Link 1]: https://leetcode-cn.com/problems/continuous-subarray-sum/solution/xiang-xi-rong-yi-li-jie-de-lian-xu-zi-shu-zu-he-xi/
[974. _ K]: https://leetcode-cn.com/problems/subarray-sums-divisible-by-k/
[1248.]: https://leetcode-cn.com/problems/count-number-of-nice-subarrays/
[713. _K]: https://leetcode-cn.com/problems/subarray-product-less-than-k/
[325. _ k]: https://leetcode-cn.com/problems/maximum-size-subarray-sum-equals-k/
[152.]: https://leetcode-cn.com/problems/maximum-product-subarray/
[238.]: https://leetcode-cn.com/problems/product-of-array-except-self/