1
template <typename T, typename Allocator = std::allocator<T>>
2
class vector {
3
    T* _begin;      // 指向第一个元素
4
    T* _end;        // 指向最后一个元素的下一位（past-the-end）
5
    T* _capacity;   // 指向分配内存块的末尾
6

7
public:
8
    // ========== 容量查询 ==========
9
    size_t size() const     { return _end - _begin; }
10
    size_t capacity() const { return _capacity - _begin; }
11
    bool empty() const      { return _begin == _end; }
12

13
    // ========== 元素访问 ==========
14
    T& operator[](size_t i)       { return _begin[i]; }        // 不做越界检查！
15
    T& at(size_t i) {                                           // 做越界检查
16
        if (i >= size()) throw std::out_of_range("vector::at");
17
        return _begin[i];
18
    }
19
    T& front() { return *_begin; }
20
    T& back()  { return *(_end - 1); }
21
    T* data()  { return _begin; }       // 获取底层裸指针
22

23
    // ========== 尾部操作 ==========
24
    void push_back(const T& value) {
25
        if (_end == _capacity) {
26
            // 容量不足，需要扩容！
27
            _grow();
28
        }
29
        *_end = value;      // 在 _end 位置构造元素
30
        ++_end;             // 移动 _end 指针
31
    }
32

33
    void pop_back() {
34
        --_end;
35
        _end->~T();          // 析构最后一个元素
36
    }
37

38
    // ========== 扩容核心 ==========
39
    void _grow() {
40
        size_t old_cap = capacity();
41
        size_t new_cap = old_cap == 0 ? 1 : old_cap * 2;  // GCC: 2倍扩容
42
        // MSVC: old_cap + old_cap / 2 (1.5倍扩容)
43

44
        T* new_buf = allocator.allocate(new_cap);          // 1. 分配新内存
45
        std::uninitialized_move(_begin, _end, new_buf);    // 2. 移动旧元素
46
        allocator.deallocate(_begin, old_cap);              // 3. 释放旧内存
47

48
        _end = new_buf + size();
49
        _begin = new_buf;
50
        _capacity = new_buf + new_cap;
51
    }
52
};

1
std::vector<int> v;
2

3
// reserve：只分配内存，不创建元素
4
v.reserve(1000);      // capacity = 1000, size = 0
5
                       // 适合：你知道大概要放多少元素
6

7
// resize：改变 size，可能创建/销毁元素
8
v.resize(100);         // capacity = 1000, size = 100
9
                       // 新元素被值初始化（int → 0）
10

11
v.resize(50);          // capacity = 1000, size = 50
12
                       // 后 50 个元素被析构
13

14
// shrink_to_fit：尝试释放多余内存（非强制）
15
v.shrink_to_fit();     // capacity ≈ 50, size = 50 (实现可以忽略这个请求)

1
// ❌ 经典错误：遍历中删除元素
2
std::vector<int> v = {1, 2, 3, 4, 5};
3
for (auto it = v.begin(); it != v.end(); ++it) {
4
    if (*it % 2 == 0) {
5
        v.erase(it);  // it 失效了！下一次 ++it 是未定义行为
6
    }
7
}
8

9
// ✅ 正确做法 1：erase 返回下一个有效迭代器
10
for (auto it = v.begin(); it != v.end(); ) {
11
    if (*it % 2 == 0) {
12
        it = v.erase(it);  // erase 返回下一个有效迭代器
13
    } else {
14
        ++it;
15
    }
16
}
17

18
// ✅ 正确做法 2：erase-remove idiom (C++17 更推荐 std::erase_if)
19
v.erase(std::remove_if(v.begin(), v.end(),
20
    [](int x) { return x % 2 == 0; }), v.end());
21

22
// ✅ 正确做法 3：C++20 std::erase_if
23
std::erase_if(v, [](int x) { return x % 2 == 0; });

1
#include <array>
2
#include <optional>
3
#include <stdexcept>
4

5
template <typename T, std::size_t Capacity>
6
class RingBuffer {
7
    static_assert(Capacity > 0, "Capacity must be > 0");
8

9
    std::array<T, Capacity> _buf{};
10
    std::size_t _head = 0;     // 下一个读取的位置
11
    std::size_t _tail = 0;     // 下一个写入的位置
12
    std::size_t _size = 0;     // 当前元素数量
13

14
    std::size_t _next(std::size_t idx) const {
15
        return (idx + 1) % Capacity;
16
    }
17

18
public:
19
    // 写入：如果满了，覆盖最旧的元素（适用于游戏帧缓冲场景）
20
    void push(const T& value) {
21
        _buf[_tail] = value;
22
        _tail = _next(_tail);
23

24
        if (_size == Capacity) {
25
            _head = _next(_head);  // 满了，头部前移（丢弃最旧元素）
26
        } else {
27
            ++_size;
28
        }
29
    }
30

31
    // 读取并移除最旧的元素
32
    std::optional<T> pop() {
33
        if (_size == 0) return std::nullopt;
34

35
        T value = _buf[_head];
36
        _head = _next(_head);
37
        --_size;
38
        return value;
39
    }
40

41
    // 查看最旧的元素（不移除）
42
    std::optional<T> peek() const {
43
        if (_size == 0) return std::nullopt;
44
        return _buf[_head];
45
    }
46

47
    std::size_t size() const { return _size; }
48
    bool empty() const { return _size == 0; }
49
    bool full() const { return _size == Capacity; }
50

51
    // 获取倒数第 n 个元素（0 = 最新的）
52
    // 游戏中常用：获取"前 N 帧"的数据
53
    const T& back(std::size_t n = 0) const {
54
        if (n >= _size) throw std::out_of_range("RingBuffer::back");
55
        std::size_t idx = (_tail + Capacity - 1 - n) % Capacity;
56
        return _buf[idx];
57
    }
58
};

1
// 对向双指针：利用有序性收缩范围
2
std::vector<int> twoSum(std::vector<int>& nums, int target) {
3
    int left = 0, right = nums.size() - 1;
4
    while (left < right) {
5
        int sum = nums[left] + nums[right];
6
        if (sum == target) {
7
            return {left + 1, right + 1};  // 题目要求 1-indexed
8
        } else if (sum < target) {
9
            ++left;   // 和太小，左指针右移
10
        } else {
11
            --right;  // 和太大，右指针左移
12
        }
13
    }
14
    return {};  // 题目保证有解
15
}
16
// 时间 O(n), 空间 O(1)

1
std::vector<std::vector<int>> threeSum(std::vector<int>& nums) {
2
    std::vector<std::vector<int>> result;
3
    std::sort(nums.begin(), nums.end());  // 必须先排序
4

5
    for (int i = 0; i < static_cast<int>(nums.size()) - 2; ++i) {
6
        if (i > 0 && nums[i] == nums[i - 1]) continue;  // 跳过重复
7

8
        int left = i + 1, right = static_cast<int>(nums.size()) - 1;
9
        while (left < right) {
10
            int sum = nums[i] + nums[left] + nums[right];
11
            if (sum == 0) {
12
                result.push_back({nums[i], nums[left], nums[right]});
13
                // 跳过重复值
14
                while (left < right && nums[left] == nums[left + 1]) ++left;
15
                while (left < right && nums[right] == nums[right - 1]) --right;
16
                ++left; --right;
17
            } else if (sum < 0) {
18
                ++left;
19
            } else {
20
                --right;
21
            }
22
        }
23
    }
24
    return result;
25
}
26
// 时间 O(n²), 空间 O(1)（不算结果）

1
int slidingWindow(std::vector<int>& nums) {
2
    int left = 0;
3
    int result = 0;
4
    // 窗口状态（根据题目定义，可能是 sum、map、set 等）
5
    int window_state = 0;
6

7
    for (int right = 0; right < nums.size(); ++right) {
8
        // 1. 扩大窗口：加入 nums[right]
9
        window_state += nums[right];
10

11
        // 2. 收缩窗口：当窗口不满足条件时
12
        while (/* 窗口不满足条件 */) {
13
            window_state -= nums[left];
14
            ++left;
15
        }
16

17
        // 3. 更新结果
18
        result = std::max(result, right - left + 1);
19
    }
20
    return result;
21
}

1
int minSubArrayLen(int target, std::vector<int>& nums) {
2
    int left = 0;
3
    int sum = 0;
4
    int min_len = INT_MAX;
5

6
    for (int right = 0; right < nums.size(); ++right) {
7
        sum += nums[right];
8

9
        while (sum >= target) {
10
            min_len = std::min(min_len, right - left + 1);
11
            sum -= nums[left];
12
            ++left;
13
        }
14
    }
15
    return min_len == INT_MAX ? 0 : min_len;
16
}
17
// 时间 O(n), 空间 O(1)

1
int longestOnes(std::vector<int>& nums, int k) {
2
    int left = 0, zeros = 0, max_len = 0;
3

4
    for (int right = 0; right < nums.size(); ++right) {
5
        if (nums[right] == 0) ++zeros;
6

7
        while (zeros > k) {
8
            if (nums[left] == 0) --zeros;
9
            ++left;
10
        }
11

12
        max_len = std::max(max_len, right - left + 1);
13
    }
14
    return max_len;
15
}
16
// 时间 O(n), 空间 O(1)

1
int subarraySum(std::vector<int>& nums, int k) {
2
    // 前缀和 + 哈希表
3
    // 核心：如果 prefix[j] - prefix[i] == k，说明 [i, j) 的和为 k
4
    //       即寻找之前出现过的 prefix[i] == prefix[j] - k
5
    std::unordered_map<int, int> prefix_count;
6
    prefix_count[0] = 1;  // 前缀和为 0 出现 1 次（空子数组）
7

8
    int sum = 0, count = 0;
9
    for (int num : nums) {
10
        sum += num;
11
        if (prefix_count.count(sum - k)) {
12
            count += prefix_count[sum - k];
13
        }
14
        ++prefix_count[sum];
15
    }
16
    return count;
17
}
18
// 时间 O(n), 空间 O(n)

1
std::vector<int> spiralOrder(std::vector<std::vector<int>>& matrix) {
2
    std::vector<int> result;
3
    if (matrix.empty()) return result;
4

5
    int top = 0, bottom = matrix.size() - 1;
6
    int left = 0, right = matrix[0].size() - 1;
7

8
    while (top <= bottom && left <= right) {
9
        // → 从左到右（上边界）
10
        for (int j = left; j <= right; ++j)
11
            result.push_back(matrix[top][j]);
12
        ++top;
13

14
        // ↓ 从上到下（右边界）
15
        for (int i = top; i <= bottom; ++i)
16
            result.push_back(matrix[i][right]);
17
        --right;
18

19
        // ← 从右到左（下边界）
20
        if (top <= bottom) {
21
            for (int j = right; j >= left; --j)
22
                result.push_back(matrix[bottom][j]);
23
            --bottom;
24
        }
25

26
        // ↑ 从下到上（左边界）
27
        if (left <= right) {
28
            for (int i = bottom; i >= top; --i)
29
                result.push_back(matrix[i][left]);
30
            ++left;
31
        }
32
    }
33
    return result;
34
}
35
// 时间 O(m*n), 空间 O(1)（不算结果）

1
// 找 target，返回下标，不存在返回 -1
2
int binarySearch(const std::vector<int>& nums, int target) {
3
    int left = 0, right = nums.size() - 1;  // [left, right] 左闭右闭
4

5
    while (left <= right) {  // 注意：<= 因为 right 是闭区间
6
        int mid = left + (right - left) / 2;  // 防溢出写法
7
        if (nums[mid] == target) {
8
            return mid;
9
        } else if (nums[mid] < target) {
10
            left = mid + 1;
11
        } else {
12
            right = mid - 1;
13
        }
14
    }
15
    return -1;
16
}

1
int search(std::vector<int>& nums, int target) {
2
    int left = 0, right = nums.size() - 1;
3

4
    while (left <= right) {
5
        int mid = left + (right - left) / 2;
6
        if (nums[mid] == target) return mid;
7

8
        // 判断哪一半是有序的
9
        if (nums[left] <= nums[mid]) {
10
            // 左半段有序
11
            if (nums[left] <= target && target < nums[mid]) {
12
                right = mid - 1;  // target 在左半段
13
            } else {
14
                left = mid + 1;   // target 在右半段
15
            }
16
        } else {
17
            // 右半段有序
18
            if (nums[mid] < target && target <= nums[right]) {
19
                left = mid + 1;   // target 在右半段
20
            } else {
21
                right = mid - 1;  // target 在左半段
22
            }
23
        }
24
    }
25
    return -1;
26
}
27
// 时间 O(log n), 空间 O(1)