equal sum – Moonstone

equal sum – Moonstone
http://www.1point3acres.com/bbs/thread-191823-1-1.html
2 一个数组里找某个index, 使sum[:i] == sum[i+1:], 也是经典题。我一开始用了O(n) space, follow up就是优化成了O(1). 
这里代码写的有点慢，但都在没给提示的前提下bug free了。
3 上道题的变种，此时要求数组和带有权重，每个nums[i]需要乘以一个weight, 这个weight等于和某个index的距离。
eg:
nums = [1, 3, 5, 7, 8]
假如当前处理到nums[2], 则leftsum = 1 * 2 + 3 * 1 = 5, rightsum = 7 * 1 + 8 * 2 = 23

public int EqualSum(int[] input)

{

    if ((input == null) || (input.Length <= 1))

    {

        return -1;

    }

 

    int sum = 0;

    int len = input.Length;

 

    for (int i = 0; i < len; i++)

    {

        sum += input[i];

    }

 

    if (sum % 2 == 1)

    {

        return -1;

    }

 

    int halfSum = sum / 2;

    int s = 0;

 

    int j = 0;

    while (j < len)

    {

        s += input[j];

        if (s == halfSum)

        {

            return j;

        }

        j++;

    }

 

    return j;

 

}

 

public int EqualSumWithWeigh(int[] input)

{

    if ((input == null) || (input.Length <= 1))

    {

        return -1;

    }

 

    int sum = 0;

    int len = input.Length;

    int[] p = new int[len];

 

    for (int i = 0; i < len; i++)

    {

        sum += input[i];

        p[i] = sum;

    }

 

    int k = 0;

    int leftSum = 0;

    int rightSum = 0;

 

    int j = k + 1;

    while (j < len)

    {

        rightSum += (j - k) * input[j];

        j++;

    }

 

    while (k <= len)

    {

        if (leftSum == rightSum)

        {

            return k;

        }

 

        k++;

        //leftSum - 0..k-1, k, k+1..N-1

        leftSum += p[k - 1];

        rightSum -= (p[len - 1] - p[k - 1]);

    }

 

    return k;

}

 

public void TestEqualSum()

{

    int[] input1 = new int[] { -2, 3, 2, 1, 2 };

    int index1 = EqualSum(input1);

}

 

public void TestEqualSumWithWeigh()

{

    int[] input1 = new int[] { 1, 3, 5, 7, 8 };

    int r1 = EqualSumWithWeigh(input1);

}

Read full article from equal sum – Moonstone