前端Jeek

数组训练

算法

🌙 数组 (opens new window)

🌙 1.合并两个有序数组 (opens new window)

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

 

示例 1：

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
  • 非原地处理，需要额外空间，正序判断
/**
 Do not return anything, modify nums1 in-place instead.
 */
function merge(nums1: number[], m: number, nums2: number[], n: number): void {
    let i=0, j = 0
    let res = []

    while(i<m && j < n) {
        if(nums1[i] <= nums2[j]) {
            res.push(nums1[i++])
        } else {
           res.push(nums2[j++]) 
        }
      
    }

    while(i<m) {
        res.push(nums1[i++])
    }

    while(j<n) {
        res.push(nums2[j++])
    }

    let k=0

    while(k<m+n) {
       nums1[k] =  res[k]
       k++
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
  • 原地处理，不需要额外空间，倒序判断
/**
 Do not return anything, modify nums1 in-place instead.
 */
function merge(nums1: number[], m: number, nums2: number[], n: number): void {
    let i = m - 1, j = n - 1
    let k = m + n - 1

    while (i >= 0 && j >= 0) {
        nums1[k--] = nums1[i] > nums2[j] ? nums1[i--] : nums2[j--]
    }

    while (j >= 0) {
        nums1[k--] = nums2[j--]
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

优化一下：

function merge(nums1: number[], m: number, nums2: number[], n: number): void {
    let i = m - 1, j = n - 1
    let k = m + n - 1

    while (j >= 0) {
        if(i>=0) {
            nums1[k--] = nums1[i] > nums2[j] ? nums1[i--] : nums2[j--]
        } else {
            nums1[k--] = nums2[j--]
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

🌙 2.最小路径和 (opens new window)

  • 回溯，把所有的路径找出来(会超时)
/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function (grid) {
        let res = []
        let path = []

        let rows = grid.length
        let cols = grid[0].length

        backtracking(res, path, grid, 0, 0, rows, cols)

        console.log(res)

        let ans = Infinity
        for (let arr of res) {
            console.log(sum(arr))
            ans = Math.min(sum(arr), ans)
        }
        return ans
    };

function sum(arr) {
    return arr.reduce((a, b) => a + b)
}

function backtracking(res, path, grid, row, col, rows, cols) {
    if (path.length === rows + cols - 1) {
        res.push([...path])
        return
    }

    if (row < rows && col < cols) {
        path.push(grid[row][col])
        backtracking(res, path, grid, row + 1, col, rows, cols)
        backtracking(res, path, grid, row, col + 1, rows, cols)
        path.pop()
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
  • 动态规划
function minPathSum(grid: number[][]): number {
    // dp方程
    // dp[i][j] = dp[i - 1][j] + grid[i][j]
    // dp[i][j] = dp[i][j - 1] + grid[i][j]
    
    // 边界情况
    // dp[0][j] = dp[0][j - 1] + grid[0][j]
    // dp[i][0] = dp[i-1][0] + grid[i][0]
    
    let rows = grid.length
    let cols = grid[0].length

    let dp = new Array(rows).fill(0).map(() => new Array(cols).fill(0))
    dp[0][0] = grid[0][0]

    for(let i=1; i<rows; i++) {
        dp[i][0] = dp[i-1][0] + grid[i][0]
    }

    for(let j=1; j<cols; j++) {
        dp[0][j] = dp[0][j-1] + grid[0][j]
    }

    for(let i=1; i<rows; i++) {
        for(let j=1; j<cols; j++) {
            dp[i][j] = Math.min(dp[i - 1][j] + grid[i][j], dp[i][j - 1] + grid[i][j])
        }
    }

    return dp[rows-1][cols-1]
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

🌙 3.两数之和 (opens new window)

function twoSum(nums: number[], target: number): number[] {
  const cache = new Map()
  
  for(let i=0; i<nums.length; i++) {
    let j = target - nums[i]
    if(cache.has(j)) {
      return [cache.get(j), i]
    }
    cache.set(nums[i], i)
  }
  return res
}
1
2
3
4
5
6
7
8
9
10
11
12

🌙 4.两数之和 II (opens new window)

function twoSum(numbers: number[], target: number): number[] {
    let left = 0
    let right = numbers.length - 1

    while(left < right) {
        let s = numbers[left] + numbers[right]
        if(s === target) {
            return [left+1, right+1]
        } else if(s < target) {
            left++
        } else {
            right--
        }
    }

    return [-1, -1]
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

🌙 5.三数之和 (opens new window)

function threeSum(nums: number[]): number[][] {
    const res: number[] = []
    // 升序排序 NlogN
    nums.sort((a: number, b: number) => a - b)

    // N * N
    for (let i = 0; i < nums.length - 2; i++) {
        if (nums[i] > 0) return res;
        // 1、跳过重复
        if (i > 0 && nums[i] === nums[i - 1]) continue;
        let left = i + 1;
        let right = nums.length - 1;
        while (left < right) {
            let sum = nums[i] + nums[left] + nums[right]
            if (sum === 0) {
                res.push([nums[i], nums[left], nums[right]]);
                left++
                right--
                // 2、跳过重复
                while (left < right && nums[left] === nums[left - 1]) {
                    left++
                }
                // 3、跳过重复
                while (left < right && nums[right] === nums[right + 1]) {
                    right--
                }

            } else if (sum > 0) {
                right--
            } else {
                left++
            }
        }
    }
    return res;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

🌙 6.四数之和 (opens new window)

  • 暴力法(超时)
function fourSum(nums: number[], target: number): number[][] {
    let res = []
    nums.sort()
    let set = new Set()
    for (let i = 0; i < nums.length - 3; i++) {
        for (let j = i + 1; j < nums.length - 2; j++) {
            for (let k = j + 1; k < nums.length - 1; k++) {
                for (let m = k + 1; m < nums.length; m++) {
                    if (nums[i] + nums[j] + nums[k] + nums[m] === target) {
                        if (!set.has(`${nums[i]},${nums[j]},${nums[k]},${nums[m]}`)) {
                            res.push([nums[i], nums[j], nums[k], nums[m]])
                            set.add(`${nums[i]},${nums[j]},${nums[k]},${nums[m]}`)
                        }
                    }
                }
            }
        }
    }

    return res
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
  • 参考三数之和，先排序，set去重
function fourSum(nums: number[], target: number): number[][] {
    const res: number[][] = []
    // 升序排序 NlogN
    nums.sort((a: number, b: number) => a - b)
    // 去重处理（此处可优化）
    let set = new Set()
    for (let i = 0; i < nums.length - 3; i++) {
        for (let j = i + 1; j < nums.length - 2; j++) {
            let m = j + 1, n = nums.length - 1

            while (m < n) {
                let sum = nums[i] + nums[j] + nums[m] + nums[n]

                if (sum === target) {
                    if (!set.has([nums[i], nums[j], nums[m], nums[n]].toString())) {
                        res.push([nums[i], nums[j], nums[m], nums[n]])
                        set.add([nums[i], nums[j], nums[m], nums[n]].toString())
                    }
                    m++
                    n--
                    while (nums[m] === nums[m - 1]) {
                        m++
                    }
                    while (nums[n] === nums[n + 1]) {
                        n--
                    }
                } else if (sum > target) {
                    n--
                } else {
                    m++
                }

            }
        }
    }

    return res
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
  • 参考三数之和，先排序，优化去重逻辑
function fourSum(nums: number[], target: number): number[][] {
    const res: number[][] = []
    // 升序排序 NlogN
    nums.sort((a: number, b: number) => a - b)
    let len = nums.length
    for (let i = 0; i < len - 3; i++) {
        if (i > 0 && nums[i] === nums[i - 1]) continue; // 跳过重复数字
        if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break; // 优化一
        if (nums[i] + nums[len - 3] + nums[len - 2] + nums[len - 1] < target) continue; // 优化二

        for (let j = i + 1; j < len - 2; j++) {
            if (j > i + 1 && nums[j] === nums[j - 1]) continue; // 跳过重复数字
            if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) break; // 优化一
            if (nums[i] + nums[j] + nums[len - 2] + nums[len - 1] < target) continue; // 优化二

            let m = j + 1, n = nums.length - 1

            while (m < n) {
                let sum = nums[i] + nums[j] + nums[m] + nums[n]

                if (sum === target) {
                    res.push([nums[i], nums[j], nums[m], nums[n]])
                    m++
                    n--
                    while (m < n && nums[m] === nums[m - 1]) {
                        m++
                    }
                    while (m < n && nums[n] === nums[n + 1]) {
                        n--
                    }
                } else if (sum > target) {
                    n--
                } else {
                    m++
                }

            }
        }
    }

    return res
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

🌙 7.滑动窗口的最大值 (opens new window)

  • 大顶堆
function maxSlidingWindow(nums: number[], k: number): number[] {
    const result = []

    type MaxHeapItem = { value: number, index: number }
    const maxHeap = new MaxHeap<MaxHeapItem>({compareFn: (a: MaxHeapItem, b: MaxHeapItem) => a.value - b.value})

    // 前k个元素
    for (let i = 0; i < k; i++) {
        maxHeap.push({value: nums[i], index: i})
    }
    // 前k个元素的最大值
    result.push(maxHeap.peek().value)

    // 开始滑动
    for (let i = k; i < nums.length; i++) {
        maxHeap.push({value: nums[i], index: i})
        // 最大值不在滑动窗口中，则从堆顶移除
        while (maxHeap.peek().index <= i - k) {
            maxHeap.pop()
        }
        // 移除之后，获取当前堆顶的值
        result.push(maxHeap.peek().value)
    }
    return result
}

class MaxHeap<T> {
    private readonly maxHeap: T[]
    private readonly compareFn: ((a: T, b: T) => number) | undefined

    constructor(param?: { data?: T[]; compareFn?: (a: T, b: T) => number }) {
        this.maxHeap = param?.data ? [...param?.data] : [];
        this.compareFn = param?.compareFn;

        // 从后往前堆化非叶子节点
        for (let i = this.parent(this.size() - 1); i >= 0; i--) {
            this.siftDown(i)
        }
    }

    private compare(a: T, b: T): number {
        if (this.compareFn) {
            return this.compareFn(a, b)
        } else if (typeof a === 'number' && typeof b === 'number') {
            return a - b
        } else {
            throw new Error('请传入 compareFn 或 number数组');
        }
    }

    // 获取节点索引为i的父节点索引
    private parent(i: number): number {
        return Math.floor((i - 1) / 2);
    }

    // 获取节点索引为i的左子节点索引
    private left(i: number): number {
        return i * 2 + 1;
    }

    // 获取节点索引为i的右子节点索引
    private right(i: number): number {
        return i * 2 + 2;
    }

    public size(): number {
        return this.maxHeap.length
    }

    public isEmpty(): boolean {
        return this.size() === 0;
    }

    public peek(): T {
        return this.maxHeap[0];
    }

    // 从节点i开始，从顶至底堆化
    private siftDown(i: number) {
        while (true) {
            const left = this.left(i)
            const right = this.right(i)

            let max = i

            if (left < this.size() && this.compare(this.maxHeap[left], this.maxHeap[max]) > 0) {
                max = left
            }

            if (right < this.size() && this.compare(this.maxHeap[right], this.maxHeap[max]) > 0) {
                max = right
            }
            if (max === i) break;
            this.swap(i, max)
            i = max
        }
    }

    private swap(i: number, j: number) {
        [this.maxHeap[i], this.maxHeap[j]] = [this.maxHeap[j], this.maxHeap[i]]
    }

    // 元素入堆
    public push(val: T) {
        // 添加节点
        this.maxHeap.push(val);
        // 从底至顶堆化
        this.siftUp(this.size() - 1);
    }

    private siftUp(i: number): void {
        while (true) {
            // 获取节点 i 的父节点
            const p = this.parent(i);
            // 当“越过根节点”或“节点无须修复”时，结束堆化
            if (p < 0 || this.compare(this.maxHeap[i], this.maxHeap[p]) <= 0) break;
            // 交换两节点
            this.swap(i, p);
            // 循环向上堆化
            i = p;
        }
    }

    // 元素出堆
    public pop(): T | undefined {
        // 判空处理
        if (this.isEmpty()) throw new RangeError('Heap is empty.');
        // 交换根节点与最右叶节点（交换首元素与尾元素）
        this.swap(0, this.size() - 1);
        // 删除节点
        const val = this.maxHeap.pop();
        // 从顶至底堆化
        this.siftDown(0);
        // 返回堆顶元素
        return val;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
  • 单调递减队列(双端队列)
function maxSlidingWindow(nums: number[], k: number): number[] {
    let res = []
    let len = nums.length
    if (len < 1) return res

    // 单调队列(双端队列)
    let queue = []

    for (let i = 0; i < len; i++) {
        // 保证单调递减队列
        while (queue.length > 0 && nums[queue[queue.length - 1]] < nums[i]) {
            queue.pop()
        }
        queue.push(i)

        // 滑动窗口向右边移动，移除最左边的元素， 注意index
        if (queue.length > 0 && queue[0] < i - limit + 1) {
            queue.shift()
        }

        // 滑动窗口元素到达limit值，需要记录当前最大的元素
        if (queue.length > 0 && i + 1 >= limit) {
            res.push(nums[queue[0]])
        }
    }

    return res
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

🌙 8.最长上升子序列 (opens new window)

🌙 9.最长公共前缀 (opens new window)

🌙 10.最长公共子序列 (opens new window)

/**
 * @param {string} text1
 * @param {string} text2
 * @return {number}
 */
var longestCommonSubsequence = function(text1, text2) {
    let len1 = text1.length;
    let len2 = text2.length;

    let dp = new Array(len1 + 1).fill(0).map(d => new Array(len2 + 1).fill(0));

    for(let i=1; i<=len1; i++) {
        for(let j=1; j<=len2; j++) {
            if(text1[i-1] === text2[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }

    return dp[len1][len2];
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

DP Table练习工具 (opens new window)

🌙 11.乘积最大子数组 (opens new window)

🌙 12.俄罗斯套娃信封问题【排序+最长上升子序列】 (opens new window)


/**
 * @param {number[][]} envelopes
 * @return {number}
 */
var maxEnvelopes = function(envelopes) {
  if (envelopes.length === 1) return 1;
    // 安左侧升序，相同，安右侧降序
    // [1,5],[2,5],[2,4], [3,4]
    envelopes.sort((a, b) => {
        if (a[0] !== b[0]) return a[0] - b[0];
        else return b[1] - a[1];
    });
    let LISArr = [];
    for (let [key, value] of envelopes) {
      LISArr.push(value);
    }
    console.log( LISArr);
    return LIS(LISArr);
};
  // 计算最长上升子序列
function LIS(arr) {
  let dp = [];
  let maxAns = 0;
  for (let i = 0; i < arr.length; i++) {
    dp[i] = 1;
  }
  for (let i = 1; i < arr.length; i++) {
    for (let j = i; j >= 0; j--) {
      if (arr[i] > arr[j]) {
        dp[i] = Math.max(dp[i], dp[j] + 1)
      }
      maxAns = Math.max(maxAns, dp[i]);
    }
  }
  return maxAns;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

🌙 13.最长连续递增序列【快慢指针】 (opens new window)


/**
 * @param {number[]} nums
 * @return {number}
 */
var findLengthOfLCIS = function(nums) {
    if (nums.length === 0) return 0;
    const n = nums.length;
    let left = 0, right = 1;
    let globalMaxLen = 1, maxLen = 1;
    while (right < n) {
        if (nums[right] > nums[left]) maxLen++;
        else {
            maxLen = 1;
        }
        left++;
        right++;
        globalMaxLen = Math.max(globalMaxLen, maxLen);
    }
    return globalMaxLen;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

🌙 14.最长连续序列 【哈希表】 (opens new window)


/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function(nums) {
    if (nums.length === 0) return 0;
    const set = new Set(nums);
    const n = nums.length;
    let globalLongest = 1;
    for (let i = 0; i < n; i++) {
        if (!set.has(nums[i] - 1)) {
            let longest = 1;
            let currentNum = nums[i];
            while (set.has(currentNum + 1)) {
                currentNum += 1;
                longest++;
            }
            globalLongest = Math.max(globalLongest, longest);
        }
    }
    return globalLongest;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

🌙 15.盛最多水的容器【双指针】 (opens new window)

左右双指针解法：


/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
    let n = height.length;
    let left = 0, right = n - 1;
    let maxOpacity = 0;
    while (left < right) {
        let res = Math.min(height[left], height[right]) * (right - left);
        maxOpacity = Math.max(maxOpacity, res);
        if (height[left] < height[right]) left++
        else right--;
    }
    return maxOpacity;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

🌙 16.删除有序数组中的重复项【快慢指针】 (opens new window)


/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
  if (nums.length <= 1) return nums.length;
  let lo = 0, hi = 0;
  while (hi < nums.length) {
    while (nums[lo] === nums[hi] && hi < nums.length) hi++;
    if (nums[lo] !== nums[hi] && hi < nums.length) {
      lo++;
      nums[lo] = nums[hi];
    }
    hi++;
  }
  return lo + 1;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

🌙 17.和为K的子数组【哈希表】 (opens new window)


/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraySum = function(nums, k) {
    let cnt = 0;
    let sum0_i = 0, sum0_j = 0;
    let map = new Map();
    map.set(0, 1);
    for (let i = 0; i <= nums.length; i++) {
        sum0_i += nums[i];
        sum0_j = sum0_i - k;
        console.log('map', sum0_j, map.get(sum0_j))
        if (map.has(sum0_j)) {
            cnt += map.get(sum0_j);
        }
        let sumCnt = map.get(sum0_i) || 0;
        map.set(sum0_i, sumCnt + 1);
    }
    return cnt;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

🌙 17.接雨水【双指针】 (opens new window)


/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
    let ans = 0;
    let left = 0, right = height.length - 1;
    let leftMax = 0, rightMax = 0;
    while (left < right) {
        leftMax = Math.max(leftMax, height[left]);
        rightMax = Math.max(rightMax, height[right]);
        if (height[left] < height[right]) {
            ans += leftMax - height[left];
            ++left;
        } else {
            ans += rightMax - height[right];
            --right;
        }
    }
    return ans;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

🌙 18.跳跃游戏(贪心) (opens new window)


/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function(nums) {
    let faster = 0;
    for (let i = 0; i < nums.length - 1; i++) {
        faster = Math.max(faster, i + nums[i]);
        if (faster <= i) return false;
    }
    return faster >= nums.length - 1;
};
1
2
3
4
5
6
7
8
9
10
11
12
13

🌙 19.用最少数量的箭引爆气球 (opens new window)


/**
 * @param {number[][]} points
 * @return {number}
 */
var findMinArrowShots = function(points) {
  if(points.length < 1) return 0;

  points.sort((a,b) => a[0] - b[0]);

  let ans = 1;

  for(let i=1; i<points.length; i++) {
    if(points[i][0] > points[i-1][1]) {
      ans++;
    } else {
      points[i][1] = Math.min(points[i][1], points[i-1][1])
    }
  }

  return ans;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

🌙 20.合并区间 (opens new window)

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function(intervals) {
  if(intervals.length < 2) return intervals;
  intervals.sort((a,b) => a[0] - b[0]);

  let ans = [intervals[0]];

  for(let i=1; i<intervals.length; i++) {
    let last = ans[ans.length - 1];
    if(last[1] >= intervals[i][0]) {
      last[1] = Math.max(last[1], intervals[i][1])
    } else {
      ans.push(intervals[i])
    }
  }

  return ans;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

🌙 21.在排序数组中查找元素的第一个和最后一个位置 (opens new window)


/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function(nums, target) {
    const left = leftBound(nums, target);
    const right = rightBound(nums, target);
    return [left, right];
};
function leftBound(nums, target) {
    let left = 0;
    let right = nums.length - 1;
    while (left <= right) {
        let mid = Math.floor(left + (right - left) / 2);
        if (nums[mid] === target) {
            right = mid - 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        }
    }
    if (left >= nums.length || nums[left] !== target) {
        return -1;
    }
    return left;
}
function rightBound(nums, target) {
    let left = 0;
    let right = nums.length - 1;
    while (left <= right) {
        let mid = Math.floor(left + (right - left) / 2);
        if (nums[mid] === target) {
            left = mid + 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        }
    }
    if (right < 0 || nums[right] !== target) {
        return -1;
    }
    return right;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

链表训练