Python世界：力扣题解1712，将数组分成三个子数组的方案数，中等

任务背景

---

问题来自力扣题目1712. Ways to Split Array Into Three Subarrays，大意如下：

A split of an integer array is good if:

• The array is split into three non-empty contiguous subarrays - named left, mid, right respectively from left to right.
• The sum of the elements in left is less than or equal to the sum of the elements in mid, and the sum of the elements in mid is less than or equal to the sum of the elements in right.

Given nums, an array of non-negative integers, return the number of good ways to split nums. As the number may be too large, return it modulo 10^9 + 7.

翻译下，需求是：对给定无序数组划分成三组子数组，划分后要求左、中、右数组元素和递增，返回可划分的方法总数，若不可划分，则返回-1.

思路分析

---

第一个坑，读题失误，不是元素个数和递增，而是元素之和要递增。下面为错误做法，埋坑警戒。

import math

class Solution(object):
    def waysToSplit(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        res = 0
        nums_len = len(nums)
        ways_total = 0
        left_max = nums_len // 3 + 1
        for l in range(1, left_max):
            mid_max = (nums_len - l) // 2 + 1
            for m in range(l, mid_max):
                r = nums_len - l - m
                if (l <= m) and (m <= r) and (l + m + r == nums_len):
                    ways_total += 1
        res = ways_total
        return res

搞清楚真正意图后，思路如下：

• 先获取一个同样大小sum_arr数组，累加nums的元素和，构造有序数组，创造二分条件
• 对sum_arr数组做两个划分，即插两个板子，先定左板依次向右遍历
• 再浮动右板，找到第一个大于左板划分子数组mid，即找数组左上界low
• 再移动右板，找到第一个超过右板划分子数组right，即找数组右上界high
• 区间长度len=high-low，即为该定左板的可划分总数
• 依次移动左板，重复此步骤，累加len得到总的split_ways

代码实现

---

# nums，升序；找到第一个大于target值的索引
def get_array_left_bound(nums, l, h, t):
    # range: [low, high)
    target = t
    low = l
    high = h

    found_flag = False
    while (low < high):
        mid = low + (high - low) // 2
        if (nums[mid] >= 2*target):
            high = mid
            found_flag = True
        else:
            low = mid + 1

    if found_flag:
        return low
    return -1


# nums，升序；找到最后一个大于target值的索引
def get_array_right_bound(nums, l, h, t):
    # range: [low, high)
    tar = t
    low = l
    high = h

    # range: [low, high)
    found_flag = False
    while (low < high):
        mid = low + (high - low) // 2
        acc = nums[mid] - nums[l]
        left = acc + tar
        right = nums[h - 1] - nums[mid]
        if (left > right): # 不满足预期，缩减右界
            high = mid
        else: # 若 left <= right
            low = mid + 1
            found_flag = True
    if low > h - 1:
        low = h - 1
    if found_flag:
        return low  # 返回low-1则表示right右界，能取到；返回low，则表示右界临界值，无法取。
    return -1


def get_array_sum(nums):
    nums_len = len(nums)
    nums_sum = []
    val_sum = 0
    for i in range(nums_len):
        val_sum += nums[i]
        nums_sum.append(val_sum)
    # print(nums_sum)
    return nums_sum


def get_ways(nums, l):
    h = len(nums)
    t = nums[l] # left res, 0-l
    start = get_array_left_bound(nums, l + 1, h, t)
    # start最大只能为倒数第二个索引，要确保最后至少有一个子数组
    if (start < 1 or start + 1 >= h):
        return 0

    t = nums[start] - nums[l] # mid res, [l+1, start]
    end = get_array_right_bound(nums, start, h, t)
    if (end <= start): # start最远能偏移的边界
        return 0

    ways = end - start
    return ways


# sum + binary
class Solution(object):
    def waysToSplit(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        res = 0
        nums_len = len(nums)
        nums_sum = get_array_sum(nums)

        # 左右边界挡板
        ways_total = 0
        left_max = nums_len - 1
        for l in range(0, left_max):
            if (2*nums_sum[l] > nums_sum[nums_len - 1]):
                break
            ways_total += get_ways(nums_sum, l)
        res = ways_total % 1_000_000_007
        return res

这里也埋了个坑，最开始94行没有注意处理大数取余10^9+7，导致[0, 0, 0, 0, 0, …]大数用例一直无法通过。

测试套件

---

单例测试demo：

# one case test
nums = [1,1,1]
nums = [1,2,2,2,5,0]
nums = [3,2,1]
nums = [0,0,0,0]
nums = [0, 0, 0, 0] # 3
nums = [0, 0, 0, 0, 0] # 6

sol = Solution()
res = sol.waysToSplit(nums)
print(res)

套件测试demo：

# 导入单元测试
import unittest


def test_base(self, nums, ret):
    sol = Solution()
    res = sol.waysToSplit(nums)
    self.assertEqual(res, ret)


# 编写测试套
class TestSol(unittest.TestCase):
    def test_special1(self):
        nums = [1,1,1]
        ret = 1
        test_base(self, nums, ret)

    def test_special2(self):
        nums = [0,0,0]
        ret = 1
        test_base(self, nums, ret)

    def test_special3(self):
        nums = [0,0,0,0]
        ret = 3
        test_base(self, nums, ret)

    def test_special4(self):
        nums = [0,0,0,0,0]
        ret = 6
        test_base(self, nums, ret)

    def test_common1(self):
        nums = [1,2,2,2,5,0]
        ret = 3
        test_base(self, nums, ret)

    def test_common2(self):
        nums = [3,2,1]
        ret = 0
        test_base(self, nums, ret)

    def test_common3(self):
        nums = [1,2,2,2,5,0]
        ret = 3
        test_base(self, nums, ret)
        
        
# 含测试套版本主调
if __name__ == '__main__':
    print('start!')
    unittest.main() # 启动单元测试
    print('done!')

本文小结

---

此题关键点在于二分法左右边界的获取，需要对边界条件有很熟练的处理，同时注意题意处理和特殊用例，如全零大数组处理，可用排列组合Cm2公式来处理，获取理论值。

1. 参考实现1：https://leetcode.com/problems/ways-to-split-array-into-three-subarrays/solutions/999157/python3-binary-search-2-pointer/
2. 参考实现2：https://blog.csdn.net/weixin_59916649/article/details/125187567

原文地址：https://blog.csdn.net/qq_17256689/article/details/143694817

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！