零和SubArray

Question

数组包含正元素和负元素,找到其总和等于0的子数组.

Answer 1

当前接受的答案中的链接需要注册成员资格而我不是其内容.

该算法将找到所有具有和0的子阵列,并且可以很容易地修改它以找到最小的子阵列或跟踪起始和结束索引.该算法是O(n).

给定一个int[] input数组,您可以创建一个int[] tmp数组,其中tmp[i] = tmp[i - 1] + input[i];tmp的每个元素将存储该元素的输入总和(数组的前缀和).

现在,如果您检查tmp,您会注意到可能存在彼此相等的值.假设这个值在索引处j an k with j < k,那么输入j的总和等于sum k和,这意味着数组之间的部分之j和k为0!具体而言,0和子阵列将从索引j + 1到k.

• 注意:if j + 1 == k,k is 0那就是它!;)
• 注意:算法应考虑虚拟tmp[-1] = 0;
• 注意:一个空数组的总和为0,它是最小的,这个特殊情况也应该在面试中提出来.然后面试官会说这不算数,但这是另一个问题!;)

实现可以通过不同的方式完成,包括使用带对的HashMap,但要注意上面的NOTE部分中的特殊情况.

例:

int[] input = {4,  6,  3, -9, -5, 1, 3, 0, 2}
int[] tmp =   {4, 10, 13,  4, -1, 0, 3, 3, 5}

• 在索引0和3的tmp中的值4 ==>和tmp 1到3 = 0,长度(3 - 1)+ 1 = 3
• 索引5处tmp中的值0 ==>总和tmp 0到5 = 0,长度(5 - 0)+ 1 = 6
• 在索引6和7的tmp中的值3 ==>和tmp 7到7 = 0,长度(7 - 7)+ 1 = 1

********更新

假设在我们的tmp数组中,我们最终得到了具有相同值的多个元素,那么你必须考虑它中的每个相同的对!示例(请记住索引'-1'处的虚拟'0'):

int[] array = {0, 1, -1, 0}
int[] tmp = {0, 1, 0, 0}

通过应用上述相同的算法,0-sum子阵列由以下索引(包括)分隔:

[0] [0-2] [0-3] [1-2] [1-3] [3]

虽然具有相同值的多个条目的存在可能会影响算法的复杂性,具体取决于实现,但我相信通过在tmp上使用反向索引(将值映射到它出现的索引),我们可以将运行时间保持在上).

Answer 2

这与Gevorg建议的行相同,但我使用哈希映射进行快速查找.O(n)复杂性虽然使用了额外的空间.

private static void subArraySumsZero()
{
    int [] seed = new int[] {1,2,3,4,-9,6,7,-8,1,9};
    int currSum = 0;
    HashMap<Integer, Integer> sumMap = new HashMap<Integer, Integer>();
    for(int i = 0 ; i < seed.length ; i ++)
    {
        currSum += seed[i];
        if(currSum == 0)
        {
            System.out.println("subset : { 0 - " + i + " }");
        }
        else if(sumMap.get(currSum) != null)
        {
            System.out.println("subset : { " 
                                + (sumMap.get(currSum) + 1) 
                                + " - " + i + " }");
            sumMap.put(currSum, i);
        }
        else
            sumMap.put(currSum, i);
    }
    System.out.println("HASH MAP HAS: " + sumMap);
}

生成的输出具有元素索引(基于零):

subset : { 1 - 4 }
subset : { 3 - 7 }
subset : { 6 - 8 }

Answer 3

1. Given A[i]
  A[i] | 2 |  1 | -1 | 0 | 2 | -1 | -1
-------+---|----|--------|---|----|---
sum[i] | 2 |  3 |  2 | 2 | 4 |  3 |  2

2. sum[i] = A[0] + A[1] + ...+ A[i]
3. build a map<Integer, Set>
4. loop through array sum, and lookup map to get the set and generate set, and push <sum[i], i> into map.

Complexity O(n)