java - 找到给定总和的最宽子数组(数组切片)

Question

我最近偶然发现了一个修改过的 maximum sum subarray problem ，在这里我们知道总和(假设它是 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;

最好的问候

Answer 1

也可以在 O(n) 中完成:

首先，创建一个辅助数组，对数组的每个前缀求和:

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

以上可以在O(n)中计算时间。

接下来，创建 HashMap 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);
}

现在，迭代总和数组，并为每个元素 x ，检查 map 是否包含键 k这样 x-k == S .
这是通过检查它是否有一个键来完成的 k = S-x ，这是 HashMap 中的 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 , 这是 i 的元素在主循环中引用，它始终被视为候选者。
对于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));
}