这个将数组分成 2 个数组并将它们相加的程序的时间复杂度是多少，减少它的最佳方法是什么？

Question

给定一个整数数组（可能包括重复的整数），确定是否有办法将该数组拆分为两个子序列 A 和 B，使得两个数组中的整数之和相同，并且所有A 中的整数严格小于 B 中的所有整数。

示例 1

arr = [1, 5, 7, 1] 输出=真

我们可以将数组拆分为 A = [1, 1, 5] 和 B = [7]。

示例 2

arr = [12, 7, 6, 7, 6] 输出=假

我们不能将数组拆分为 A = [6, 6, 7] 和 B = [7, 12] 因为这不满足 A 中所有整数都小于 B 中所有整数的要求.

def f(arr):
    arr = sorted(arr)
    
    pos = 0
    sum_l, sum_r = 0, 0

    while pos < (len(arr)-1):
        sum_l, sum_r = sum(arr[:pos+1]), sum(arr[pos+1:])
        pos += 1
        if sum_l == sum_r:
            return True
    return False

我的想法是排序是O(nlogn)，while循环是O(n)，那么arr[:pos+1]整体是O(n)，arr[pos+1:]也是O(n ) 总的来说，所以加在一起是 O(nlogn) + O(n*(n+n)) = O(nlogn) + O(n^2)。对吗？

此外，有没有办法摆脱这个切片运算符以降低复杂性？

Answer 1

降低复杂度的一个简单方法是避免在每次迭代时重复计算：

def foo(arr):
    arr = sorted(arr)
    sum_l = 0
    sum_r = sum(arr)
    for val in arr:
        sum_l += val
        sum_r -= val
        if sum_l == sum_r:
            return True
    return False

但是，第二个示例的输出不正确。您可能需要调整算法。

这个将数组分成 2 个数组并将它们相加的程序的时间复杂度是多少，减少它的最佳方法是什么？

What is the time complexity of this program that slices array into 2 arrays and sums them and what would be the best way to reduce it?

python

arrays

time-complexity