找到给定和的最宽子数组（数组切片）

Question

找到给定和的最宽子数组（数组切片）

4

我最近遇到了一个修改过的最大子串和问题，在这里我们已知和（假设为S=2），但需要找到一个产生这个确切和的最长数组片段（最长意味着必须具有最大的元素数量）。

因此，对于输入数组：

A = [1, 0, -1, 1, 1, -1, -1]

我们找到了2个切片：A(0:4)，因为sum(1,0,-1,1,1)是2，以及A(3:4)，因为sum(1,1)也是2。但是A(0:4)子数组是最长的，因此它的长度5是答案。大多数我找到的解决方案不是O(n)，因为它们使用了2个循环，而不是一个循环或一些集合包。这种问题的这个变体是否可能用O(n)复杂度解决？我主要对Java编写的解决方案感兴趣，但不知道要建模哪个算法。

assert solution(new int[] { 1, 0, -1, 1, 1, -1, -1 }, 2) == 5;

最好的问候

- oski86

2个回答

-1

想象一下这样的情况：

如果你有一个数组T[A:D]，并且T[A:D]的最大子数组是T[B:C]，那么当你得到下一个元素T[E]时，你需要的是[A:E]的最大子数组，这个子数组必须是旧的T[B:C]或者是新的T[B:E]。

- rainer rainer

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- amit · Accepted Answer

这也可以用O(n)的时间复杂度来完成：

首先，创建一个辅助数组，用于计算数组的每个前缀和：

sums[i] = arr[0] + arr[1] + ... + arr[i]

以上可以在O(n)时间内计算出来。

接下来，创建一个哈希映射Map<Integer,List<Integer>>，其中键表示前缀和，值是具有此前缀和的索引列表。伪代码：

Map<Integer,List<Integer>> map = new HashMap<>();
for (int i = 0; i < sums.length; i++) {
   List<Integer> l = map.get(sums[i]);
   if (l == null) { 
       l = new ArrayList<>();
       map.put(sums[i],l);
   }
   l.add(i);
}

现在，遍历sums数组，对于每个元素x，检查map是否包含一个键k，使得x-k==S。这可以通过检查是否有一个键k=S-x来完成，在哈希映射中为O(1)。

如果存在这样的键，则获取值列表中的最后一个索引，这也可以在O(1)时间内完成，并将其作为候选匹配项。

伪代码:

int currentMaxLength = Integer.MIN_VALUE;
for (int i = 0; i < sums.length; i++) { 
   int k = S-sums[i];
   List<Integer> l = map.get(k);
   if (l == null) continue;
   int width = Math.abs(l.getLast() -  i);
   if (width > currentMaxLength) currentMaxLength = width;
}
return currentMaxLength;

这个想法是，如果你有多个匹配项对于一些x1, x2，这样的x2-x1 = S，其中x1, x2是前缀和，则最长子数组的候选者是第一个出现x1的位置，以及最后出现x2的位置。
对于x1，它是主循环中所引用的元素，并且它始终被视为候选项。
对于x2，您将始终检查x2的最后出现位置，因此这是正确的。

快速提示：实际代码还需要考虑sums[-1] = 0。

Java代码：

public static int solution(int[] arr, int S) { 
    int[] sums = new int[arr.length+1];
    int sum = 0;
    //generate the sums array:
    sums[0] = 0;
    for (int i = 0; i < arr.length; i++) sums[i+1] = sum = sum+arr[i];
    //generate map:
    Map<Integer,List<Integer>> map = new HashMap<>();
    for (int i = 0; i < sums.length; i++) {
       List<Integer> l = map.get(sums[i]);
       if (l == null) { 
           l = new ArrayList<>();
           map.put(sums[i],l);
       }
       l.add(i);
    }
    //find longest:
    int currentMaxLength = Integer.MIN_VALUE;
    for (int i = 0; i < sums.length; i++) { 
       int k = S - sums[i];
       List<Integer> l = map.get(k);
       if (l == null) continue;
       int width = Math.abs(l.get(l.size()-1) -  i);
       if (width > currentMaxLength) currentMaxLength = width;
    }
    return currentMaxLength;
}
public static void main(String[] args) {
    System.out.println(solution(new int[] { 1, 0, -1, 1, 1, -1, -1 }, 2));
}