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
Read full article from 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[] 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
);
}