## Thursday, June 9, 2016

### equal sum – Moonstone

equal sum – Moonstone
2 一个数组里找某个index, 使sum[:i] == sum[i+1:], 也是经典题。我一开始用了O(n) space, follow up就是优化成了O(1).

3 上道题的变种，此时要求数组和带有权重，每个nums[i]需要乘以一个weight, 这个weight等于和某个index的距离。
eg:
nums = [1, 3, 5, 7, 8]

`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[] input``1` `= new int[] { ``-2``, ``3``, ``2``, ``1``, ``2` `};`
`    ``int index``1` `= EqualSum(input``1``);`
`}`

`public void TestEqualSumWithWeigh()`
`{`
`    ``int[] input``1` `= new int[] { ``1``, ``3``, ``5``, ``7``, ``8` `};`
`    ``int r``1` `= EqualSumWithWeigh(input``1``);`
`}`