时间戳

首页 > 解决方案 > 如何找到给定总和的子数组

python - 如何找到给定总和的子数组

问题描述

代码如下

找到与给定总和匹配的子数组

arr 是给定数组，s 是总和

def getsub(arr,s):
    result = []
    for x in range(len(arr)):
        result.append(arr[x])
        while sum(result) > s:
            result.pop(0)
        if sum(result) == s:
            return result
arr = [4, 1, 6, 5, 2, 3]
s=5
getsub(arr,s)

我只得到[4,1]了first occurance

但实际输出是[4,1] [5] [2,3]

我可以在 o(n) 时间内完成吗？我通过打印所有子数组并检查等于 s 的和来完成 (o(n3))TC。这不是最佳的

标签： python

解决方案

可能有两种可能的方法。

  1. 滑动窗口
  2. 散列

滑动窗口：

# Function to find sublist having a given sum using hashing sliding window
def find_sub_list_using_sliding_window(arr, expected_sum):
 
    # maintains the sum of the current window
    windowSum = 0
 
    # maintain a window `[low, high-1]`
    [low, high] = [0, 0]

    # store pairs equivalent to `expected_sum`
    sum_list = []
 
    # consider every sublist starting from `low` index
    for low in range(len(arr)):
 
        # if the current window's sum is less than the given sum,
        # then add elements to the current window from the right
        while windowSum < expected_sum and high < len(arr):
            windowSum += arr[high]
            high = high + 1
 
        # if the current window's sum is equal to the given sum
        if windowSum == expected_sum:
            s_index = low
            e_index = high - 1
            sum_list.append([arr[s_index], arr[e_index]] if s_index != e_index else [arr[s_index]])
 
        # at this point, the current window's sum is more than the given sum.
        # remove the current element (leftmost element) from the window
        windowSum -= arr[low]

    return sum_list

上述解决方案的时间复杂度为O(n)并且不需要任何额外的空间，其中n是输入的大小。

散列：

# Function to find sublist having a given sum using hashing
def find_sub_list_using_hashing(arr, expected_sum):
 
    # insert `(0, -1)` pair into the set to handle the case when
    # a sublist with the given sum starts from index 0
    num_dict = {0: -1}
 
    # keep track of the sum of elements so far
    sum_so_far = 0
    
    # store pairs equivalent to `expected_sum`
    sum_list = []
    
    # traverse the given list
    for i in range(len(arr)):
 
        # update sum_so_far
        sum_so_far += arr[i]
 
        # if `sum_so_far - expected_sum` is seen before,
        # we have found the sublist with sum equal to `expected_sum`
        if (sum_so_far - expected_sum) in num_dict:
            s_index = num_dict.get(sum_so_far - expected_sum) + 1
            sum_list.append([arr[s_index], arr[i]] if s_index != i else [arr[i]])
 
        # insert (current sum, current index) pair into the dictionary
        num_dict[sum_so_far] = i

    return sum_list

上述解决方案的时间复杂度为O(n)，需要O(n)额外空间，其中n是输入的大小。

驱动程序代码：

if __name__ == '__main__':
 
    # a list of positive integers
    arr = [4, 1, 6, 5, 2, 3]
    expected_sum = 5

    sum_list = find_sub_list_using_sliding_window(arr, expected_sum)
    print(f'Find Sub List Equivalen to a Given Sum Using Sliding Window: {sum_list}')

    sum_list = find_sub_list_using_hashing(arr, expected_sum)
    print(f'Find Sub List Equivalen to a Given Sum Using Hasing: {sum_list}')

输出：

Find Sub List Equivalen to a Given Sum Using Sliding Window: [[4, 1], [5], [2, 3]]
Find Sub List Equivalen to a Given Sum Using Hasing: [[4, 1], [5], [2, 3]]

推荐阅读