数组06–总结

数组的理论基础

数组05–螺旋矩阵Ⅱ

59. Spiral Matrix II

描述

给定一个正整数 n，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。

示例:

输入: 3

输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]

数组04–长度最小的子数组

209. Minimum Size Subarray Sum

描述

给定一个含有 n 个正整数的数组nums和一个正整数 target ，

找出该数组中满足其sum ≥ target 的长度最小的连续子数组，并返回其长度。

如果不存在符合条件的子数组，返回 0。

示例：

输入：s = 7, nums = [2,3,1,2,4,3]

输出：2

解释：子数组 [4,3] 是该条件下的长度最小的子数组。

数组03–有序数组的平方

977. Squares of a Sorted Array

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例 1： 输入：nums = [-4,-1,0,3,10] 输出：[0,1,9,16,100] 解释：平方后，数组变为 [16,1,0,9,100]，排序后，数组变为 [0,1,9,16,100]

示例 2： 输入：nums = [-7,-3,2,3,11] 输出：[4,9,9,49,121]

数组02–移除元素

题干

1
2
3
4
5
6
7

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The relative order of the elements may be changed.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.

Return k after placing the final result in the first k slots of nums.

Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.

数组01–二分查找

1. 数组的基本理论

• 数组下标从0开始；
• 数组内存空间连续；
  • 导致数组增加和删除元素需要移动其他元素，开销很大！
  • vector 和 array 的区别：
    • vector 的底层是用array实现的，所以，vector是容器，而不是数组！
  • 数组的元素是不能删除的，只能覆盖！
• 二维数组的内存地址一般是连续的，可能不同，C++是连续的；
• 测试二维数组的内存地址空间是否连续：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# include <iostream>
using namespace std;
void test_arr() {
    int array[2][3] = {
        {0, 1, 2},
        {3, 4, 5}
    };
    cout << &array[0][0] << " " << &array[0][1] << " " << &array[0][2] << endl;
    cout << &array[1][0] << " " << &array[1][1] << " " << &array[1][2] << endl;
}

int main() {
    test_arr();
}