首页 > 前端 Javascript > 【算法】快速寻找数字数组中间位

【算法】快速寻找数字数组中间位

这是我在群里看到的一个问题，挺好的，故作一篇记录

题目

给定一个由数字组成的数组，找到一个位置，这个位置前面的所有数字之和跟这个位置之后的所有数字之和相等。

比如数组 [5,3,3,2,8,4,3,8,9,1]，则 index 为 5 的数字 4 为中间位，其左边之和 sum(5,3,3,2,8)=21，右边之和sum(3,8,9,1)=21。

分析

题目本身没什么特别的地方，就是遍历数组每一个位置做计算然后判断，循环都可以做出来。

我们要说的是其中可以优化的点，第一个是查找方法，一个个遍历肯定是最低效的方式，我们这里采用二分法，然后根据左右结果再决定下次二分位置；第二个就是计算结果的缓存，每查询一次就计算一次也是很低效的，因为其中有一些结果在前面可能都已经计算过了。

代码

没什么难度，直接上代码。

<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="ie=edge">
    <title>Document</title>
</head>

<body>
    <script>
        const data = Array.from({ length: 10 }).map(() => Math.round(Math.random() * 10))
        // const data = [1, 2, 3, 0, 6]
        const maxCursor = data.length - 1
        let cursorRecord = ''
        let cursor = Math.round(maxCursor / 2)
        cursorRecord += cursor
        let sumLeft = data.slice(0, cursor).reduce((prev, item) => prev + item, 0)
        let sumRight = data.slice(cursor + 1).reduce((prev, item) => prev + item, 0)

        function search() {
            if (sumLeft === 0 || sumRight === 0 || cursorRecord.includes(`[${cursor}]`)) {
                cursor = -1
                return false;
            }

            cursorRecord += `[${cursor}]`

            if (sumLeft === sumRight) {
                return false;
            }

            if (sumLeft > sumRight) {
                const middleCursor = Math.round(cursor / 2)
                sumLeft -= data.slice(middleCursor, cursor).reduce((prev, item) => prev + item, 0)
                sumRight += data.slice(middleCursor + 1, cursor + 1).reduce((prev, item) => prev + item, 0)
                cursor = middleCursor
                return search()
            } else {
                const middleCursor = Math.round((maxCursor + cursor) / 2)
                sumLeft += data.slice(cursor, middleCursor).reduce((prev, item) => prev + item, 0)
                sumRight -= data.slice(cursor + 1, cursor + 1).reduce((prev, item) => prev + item, 0)
                cursor = middleCursor
                return search()
            }
        }
        search()
        console.log(data)
        console.log(cursor)
    </script>
</body>

</html>