javascript - 如何返回数组可以分割的位置，使得一侧的总和等于另一侧

Question

我试图检查是否有一个地方可以分割数组，以便一个数组上的数字之和一边等于另一边的数字之和，以数组形式返回两个数组的长度，但是如果没有地方可以分割数组，则返回-1。

test('for an obvious case where the array can be split evenly', () => {
  expect(canBalance([1, 2, 3, 4, 5, 6, 6, 7, 8])).toEqual([6, 3]);
});

test('for an obvious case where the array cannot be split evenly', () => {
  expect(canBalance([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])).toBe(-1);
});

test('for when the array has all zeros with a one at the end', () => {
  expect(canBalance([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1])).toBe(-1);
});

test('for when the array has all ones but cannot be split', () => {
  expect(canBalance([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1])).toBe(-1);
});

test('for when the array has all ones but can be split', () => {
  expect(canBalance([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1])).toEqual([9, 9]);
});

test('for when the array some negative numbers', () => {
  expect(canBalance([3, 18, -5, -44, 23, 26, 20, -1, 0, -10, 30])).toEqual([10, 1]);
});

test('Alternating cases of positive and negative equivalent with 1 at the end', () => {
  expect(canBalance([-10, +10, -10, +10, -10, +10, -10, +10, -10, +10, -10, +10,
    -10, +10, -10, +10, -10, +10, -10, +10, -10, +10, 1])).toBe(-1);
});

test('for a simple case of positive and negative numbers', () => {
  expect(canBalance([1, 0, 0, -1])).toBe(-1);
});

test('for a tricky case of decimal numbers', () => {
  expect(canBalance([0.1, 0.2, 0.3])).toBe(-1);
});

到目前为止，我的方法是在变量中求总计。然后从 array[0] 到 array.length-1 相加，并每次与total/2 进行比较。

function canBalance(array) {
  //Type your solutions here
  var arrayAdd = 0;
  for(var i = 0; i<array.length-1; i++) {
    arrayAdd+=array[i];
  }
  var total = 0;
  for(var j=0; j<array.length-1; j++)  {
    total+=array[j];
    if(total==arrayAdd/2) {
      return [j+1, array.length-j-1];
    }
  }
  return -1;
}
module.exports = canBalance;

我相信它应该有效。但是，它在很多测试中都失败了

Answer 1

您可以使用从头开始的所有元素的总和构建一个数组，并检查从末尾开始是否存在相邻的总和，然后退出计数，否则返回-1。

array 1, 1, 1, 2, 1
sums  1  2  3  5  6  left
sums           3  1  right
            ^  ^     result [3, 2]

function canBalance(array) {
    var left = array.map((s => v => s += v)(0)),
        right = 0;
        i = array.length;

    while (i--) {
        right += array[i];
        if (right === left[i - 1]) return [i, array.length - i];
    }
    return -1;
}

console.log(canBalance([1, 1, 1, 2, 1])); // [3, 2]
console.log(canBalance([2, 1, 1, 2, 1])); // -1
console.log(canBalance([10, 10]));        // [1, 1]

console.log(canBalance([1, 2, 3, 4, 5, 6, 6, 7, 8])); // [6, 3]
console.log(canBalance([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])); // -1
console.log(canBalance([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1])); // -1
console.log(canBalance([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1])); // -1
console.log(canBalance([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1])); // [9, 9]
console.log(canBalance([3, 18, -5, -44, 23, 26, 20, -1, 0, -10, 30])); // [10, 1]
console.log(canBalance([-10, +10, -10, +10, -10, +10, -10, +10, -10, +10, -10, +10, -10, +10, -10, +10, -10, +10, -10, +10, -10, +10, 1])); // -1
console.log(canBalance([1, 0, 0, -1])); // -1
console.log(canBalance([0.1, 0.2, 0.3])); // -1

.as-console-wrapper { max-height: 100% !important; top: 0; }