时间戳

首页 > 解决方案 > 如何有效地找到数组中所有先前索引加起来为给定整数 N 的数字的索引？

javascript - 如何有效地找到数组中所有先前索引加起来为给定整数 N 的数字的索引？

问题描述

更新：我意识到这个问题是无效的。忽略它。我在for循环中犯了一个错误，实际上只需要大约 1 毫秒来对所有索引求和，而不是半秒，这导致我假设它可以使用二进制搜索进行优化，这不适用于这里。

假设我们有：

我们如何有效地找到indexat which sum(array[0], array[N]) > target ？在此示例中，索引将是2因为索引的总和超过了targetat 索引2。

基本上，我有一个元素的虚拟容器（它始终只呈现一小部分元素），所有这些元素都有不同的高度（36、48 等）和一个scroll返回滚动像素数量（目标）的事件，所以我试图找到容器滚动到的元素，在这个例子中，容器向下滚动85px，这意味着它滚动传递了元素2。

例子：

let target = 85
let array = [36, 48, 48, 36, 48, 48, 48, 48, 48, 48]

// Finding the element with a bruteforce method:
array[0] > target // false
array[0] + array[1] > target // false
array[0] + array[1] + array[2] > target // true
return 2

由于某种原因，尝试使用sum所有索引直到我们使用循环找到目标值for每 1000 个值需要半秒。

我不确定是否已经有一个众所周知的算法，但我认为我必须使用二进制搜索的自定义衍生形式来在几次迭代中找到索引，例如：

Divide the array in half
Sum all the indexes in the left half
If the target < sum, it means the target is in the left half, so divide it again
If the target > sum, extend the search to the right half
Repeat recursively

我已经部分创建了这个递归算法，但是当目标位于数组的“右半部分”时，我很难弄清楚如何正确target > halfSliceSum处理条件，即：

let target = 85
let array = [36, 48, 48, 36, 48, 48, 48, 48, 48, 48]
console.log(getElementIndexAtTargetPosition(array, target))

function getElementIndexAtTargetPosition(array, target) {
  // TESTS (expected results):
  // ([36, 48, 48, 36, 48, 48, 48, 48, 48, 48], 35) => return 0
  // ([36, 48, 48, 36, 48, 48, 48, 48, 48, 48], 36) => return 0
  // ([36, 48, 48, 36, 48, 48, 48, 48, 48, 48], 37) => return 1
  // ([36, 48, 48, 36, 48, 48, 48, 48, 48, 48], 84) => return 1
  // ([36, 48, 48, 36, 48, 48, 48, 48, 48, 48], 85) => return 2
  // ([36, 48, 48, 36, 48, 48, 48, 48, 48, 48], 456) => return 8

  let halfIndex = Math.round(array.length / 2)
  let halfSlice = array.slice(0, halfIndex)
  let halfSliceSum = halfSlice.reduce((a, b) => a + b, 0)
  if (array.length === 1) {
    return 0
  }
  if (target === halfSliceSum) {
    return halfIndex
  }
  else if (target < halfSliceSum) {
    return getElementIndexAtTargetPosition(halfSlice, target)
  }
  else if (target > halfSliceSum) {
    // Increase search slice by Math.round(halfIndex * 1.5)?
    // ...
  }
}

目标始终在数组内，即target <= sum(array[0], array[lastIndex])

标签： javascript

解决方案

您必须将所有单独的值相加，直到达到阈值，当您刚刚获得数组时，没有其他方法可以做到这一点。

但是，如果您必须多次执行此操作，它可以帮助将数组转换为递增和之一，然后您可以在其上运行二进制搜索（假设没有负求和因此它实际上是递增序列）。您甚至可以删除原始数组，因为您仍然可以通过计算差异来访问其值。

推荐阅读