查找包含集合中所有值的最短连续子数组的算法 [英] Algorithm to find shortest continuous subarray that contains all values from a set

问题描述

我要解决以下问题:

给出一组整数，例如{1,3,2}，以及一个随机整数数组，例如

Given a set of integers, e.g. {1,3,2}, and an array of random integers, e.g.

[1, 2, 2, -5, -4, 0, 1, 1, 2, 2, 0, 3,3]

找到包含集合中所有值的最短连续子数组.如果找不到子数组，则返回一个空数组.

Find the shortest continuous subarray that contains all of the values from the set. If the subarray can not be found, return an empty array.

结果:[1, 2, 2, 0, 3]

或

[1, 2, 2, -5, -4, 3, 1, 1, 2, 0], {1,3,2}.

结果:[3, 1, 1, 2]

我尝试了以下操作，第二个循环似乎出了点问题.我不确定我需要更改什么:

I have tried the following put there seems to be something wrong with my second loop. I'm not sure what I need to change:

def find_sub(l, s):
    i = 0
    counts = dict()
    end = 0
    while i < len(s):
        curr = l[end]
        if curr in s:
            if curr in counts:
                counts[curr] = counts[curr] + 1
            else:
                counts[curr] = 1
                i += 1
        end += 1
    curr_len = end

    start = 0
    for curr in l:
        if curr in counts:
            if counts[curr] == 1:
                if end < len(l):
                    next_item = l[end]
                    if next_item in counts:
                        counts[next_item] += 1
                    end += 1
            else:
                counts[curr] -= 1
                start += 1
        else:
            start += 1
    if (end - start) < curr_len:
        return l[start:end]
    else:
        return l[:curr_len]

推荐答案

您正在使用两指针方法，但是只能将两个索引移动一次-直到找到第一个匹配项.您应该重复move right - move left模式以获得最佳索引间隔.

You are using two-pointer approach, but move both indexes only once - until the first match found. You should repeat move right - move left pattern to get the best index interval.

def find_sub(l, s):
    left = 0
    right = 0
    ac = 0
    lens = len(s)
    map = dict(zip(s, [0]*lens))
    minlen = 100000
    while left < len(l):
        while right < len(l):
            curr = l[right]
            right += 1
            if curr in s:
                c = map[curr]
                map[curr] = c + 1
                if c==0:
                    ac+=1
                    if ac == lens:
                        break
        if ac < lens:
            break

        while left < right:
            curr = l[left]
            left += 1
            if curr in s:
                c = map[curr]
                map[curr] = c - 1
                if c==1:
                    ac-=1
                    break

        if right - left + 1 < minlen:
            minlen = right - left + 1
            bestleft = left - 1
            bestright = right

    return l[bestleft:bestright]

print(find_sub([1, 2, 2, -5, -4, 3, 1, 0, 1, 2, 2, 0, 3, 3], {1,3,2}))
print(find_sub([1, 2, 2, -5, -4, 3, 1, 0, 1, 2, 2, 1, 0, 3, 3], {1,3,2}))
>>[2, -5, -4, 3, 1]
>>[2, 1, 0, 3]

这篇关于查找包含集合中所有值的最短连续子数组的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！