代码随想录数组 01

1. 704.二分查找

题目链接: LeetCode 704. 二分查找

使用条件

二分查找需要满足以下条件：

  • 数组为有序数组
  • 数组中无重复元素

核心原则

二分法要遵循循环不变量原则，在循环中每一次的边界处理都要坚持根据区间的定义来操作，例如是左闭右开 [left, right) 还是左闭右闭 [left, right]，这点要分清楚。

我的解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func search(nums []int, target int) int {
    var start = 0
    var end = len(nums) - 1
    var mid = start + (end - start) / 2
    
    for start <= end {
        if target == nums[mid] {
            return mid
        }
        if target < nums[mid] {
            end = mid - 1
            mid = start + (end - start) / 2
        } else {
            start = mid + 1
            mid = start + (end - start) / 2
        }
    }
    return -1
}

Carl 的题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 时间复杂度: O(log n)
// 空间复杂度: O(1)
func search(nums []int, target int) int {
    left := 0                    // 初始化左边界
    right := len(nums) - 1       // 初始化右边界

    for left <= right {          // 循环逐步缩小区间范围
        mid := left + (right-left)>>1  // 求区间中点（防止溢出）

        if nums[mid] == target {       // 找到目标值
            return mid
        } else if nums[mid] < target { // 目标值在右半部分
            left = mid + 1
        } else {                       // 目标值在左半部分
            right = mid - 1
        }
    }

    return -1  // 没有找到目标值
}

复杂度分析

复杂度 值
时间复杂度 O(log n)
空间复杂度 O(1)

2. 27.移除元素

题目链接: LeetCode 27. 移除元素

解法：双指针法（快慢指针）

1
2
3
4
5
6
7
8
9
10
11
func removeElement(nums []int, val int) int {
    count := 0  // 慢指针：指向下一个要放置的位置
    
    for i := 0; i < len(nums); i++ {  // 快指针：遍历数组
        if nums[i] != val {           // 如果当前元素不等于 val
            nums[count] = nums[i]     // 将其移到前面
            count++                   // 慢指针前进
        }
    }
    return count  // 返回新数组的长度
}

核心思路

  • 慢指针 count: 指向下一个有效元素要放置的位置
  • 快指针 i: 遍历整个数组
  • 逻辑: 遇到不等于 val 的元素就移到前面

复杂度分析

复杂度 值
时间复杂度 O(n)
空间复杂度 O(1)

3. 977.有序数组的平方

题目链接: LeetCode 977. 有序数组的平方

解法：双指针法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func sortedSquares(nums []int) []int {
    left := 0                       // 左指针：指向数组最左端
    right := len(nums) - 1          // 右指针：指向数组最右端
    result := make([]int, len(nums))  // 创建结果数组
    pos := right                    // 填充位置：从后往前填充
    
    for left <= right {             // 双指针从两端向中间移动
        leftSquare := nums[left] * nums[left]    // 左端元素的平方
        rightSquare := nums[right] * nums[right] // 右端元素的平方
        
        if rightSquare > leftSquare {  // 如果右端平方更大
            result[pos] = rightSquare  // 放入结果数组
            right--                    // 右指针左移
        } else {                       // 如果左端平方更大或相等
            result[pos] = leftSquare   // 放入结果数组
            left++                     // 左指针右移
        }
        pos--  // 填充位置左移
    }
    return result
}

核心思路

  1. 数组已排序，但可能包含负数
  2. 平方后最大值一定在数组两端（最小负数或最大正数）
  3. 双指针从两端向中间移动，比较平方值
  4. 从后往前填充结果数组，保证有序性

复杂度分析

复杂度 值
时间复杂度 O(n)
空间复杂度 O(n)

为什么从后往前填充？

1
2
3
4
5
6
7
8
9
10
11
示例: nums = [-4, -1, 0, 3, 10]
              ↑              ↑
            平方=16        平方=100

比较两端平方值，较大的一定是结果数组的最后一个元素！

从后往前填充:
[_, _, _, _, 100]  ← 先填最大的
[_, _, _, 16, 100] ← 再填次大的
...
[0, 1, 9, 16, 100] ← 最后完成

总结

关键技巧

  1. 二分查找:

    • 坚持循环不变量原则
    • 注意边界条件 [left, right]
    • 防止溢出：mid = left + (right - left) / 2

  2. 双指针法:

    • 快慢指针：原地修改数组
    • 对撞指针：从两端向中间
    • 适用于有序数组问题

  3. 时间复杂度优化:

    • 二分查找：O(log n)
    • 双指针：O(n)，优于暴力 O(n²)

学习资源

更新日期: 2026-02-11