数据结构（一）—— 数组-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构（一）—— 数组。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、数组基础

数组是存放在连续内存空间上的相同类型数据的集合，也就是说数组内存空间的地址是连续的。
因为数组的在内存空间的地址是连续的，所以我们在删除或者增添元素的时候，就难免要移动其他元素的地址，注意：数组的元素是不能删的，只能覆盖。

1、数组初始化分配内存
int record[26] = {0};
2、vector排序函数：sort(A.begin(),A.end());
3、vector res = {1, 2, 3, 4};
4、vector int res(10,0); // 创建一个大小为10的vector
vector<vector> res(10, vector(10, 0)) // 创建一个10*10的二维vector
5、查找vector中的元素

vector<int>::iterator aa = find(visited.begin(), visited.end(), 5);  // 如果vector是空的，出现段错误
if (aa == visited.end())  没找到
else *aa   找到了返回值

PS：vector的底层实现是array，但严格来讲vector是容器，不是数组。之后补充
6、二维数组

int array[2][3] = {
		{0, 1, 2},
		{3, 4, 5}
    };
vector<int> res(10,0); // 创建一个大小为10的vector
vector<vector<int>> res(10, vector<int>(10, 0));

二维int型数组内存地址，相邻数组元素差了4个字节
数据结构（一）—— 数组
7、不推荐使用，但是要记住

num[i++] 先使用 i 的当前值来获取数组 num 中的元素，然后再将 i 的值加 1。也就是说，该操作会先返回 num[i]，然后将 i 增加 1。

num[++i] 先将 i 的值加 1，然后再使用新的值来获取数组 num 中的元素。也就是说，该操作会先将 i 增加 1，然后返回 num[i]。

二、题

1. 704 二分查找

前提条件：有序数组、无重复元素
着重点：
1、while的退出条件非常重要，小于等于：while(left <= right)
2、取中间值索引时非常重要：int mid = (right - left)/2 + left;
奇数个索引刚好在中间，偶数个索引在中间偏左位置

2. 27 移除元素

题目描述：给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]

双指针，感觉很难想，需要重点2刷。
核心思想：每次fast都会给slow值，除非fast指向了val
数据结构（一）—— 数组

代码如下（示例）：

int removeElement(vector<int>& nums, int val) {
    int slow = 0;
    int fast = 0;
    while(fast < nums.size()){  // 每次fast都会给slow值，除非fast指向了val
        if(nums[fast] != val){
            nums[slow] = nums[fast];
            slow++;
        }
        fast++;
    }
    return slow;
}

// 2021年第一次做
int fast = 0;
int slow = 0;
int removeElement(vector<int>& nums, int val) {
       for(fast = 0;fast<nums.size();fast++)
       {
           if(nums[fast] != val) //在快和慢没有分开时，当快指针不为val时，带着slow走
           {                     //在快和慢分开之后，，当快指针不为val，每次赋值结束，slow指针自加
               nums[slow] = nums[fast]; //只要不赋值，慢指针就永远不自加
               slow++;
           }
           //当快指针为val时，快指针自己走，第一次快与慢分开的时候就是第一次碰到val的时候
       }
       return slow;
}

3. 977 有序数组的平方

vector<int> sortedSquares(vector<int>& nums) {
    int k = nums.size() - 1;
    vector<int> res(nums.size(),0);
    int left = 0;
    int right = nums.size() - 1;
    while(right >= left){
    	if(nums[right] * nums[right] >= nums[left] * nums[left]){
            res[k] = nums[right] * nums[right];
            k--;
            right--;
        }else{
            res[k] = nums[left] * nums[left];
            k--;
            left++;
        }
    }
    return res;
}

4. 209 长度最小的子数组

题目：给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其和 ≥ target 的长度最小的连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2

这题做的时候思维僵化了，没有利用好≥这个条件，总觉得应该固定窗口的大小再滑动，没想到可以动态条件窗口的大小，用了三种解法都是暴力解，之后可以看看。
做这题时同时复习了哈希映射和earse函数：
1、earse输入的是数组的迭代器，例：vector.erase(vector.begin());
2、遍历哈希映射的方式
for (auto it = windowfalse.begin(); it != windowfalse.end(); it++)
cout << *it << endl;文章来源地址https://www.toymoban.com/news/detail-421677.html

// 必须使用单for来完成滑窗
int minSubArrayLen(int target, vector<int>& nums) {
    int res = 999999999;  //INT32_MAX
    int sum = 0;
    int k = 0;
    int left = 0;
    for (int right = 0; right < nums.size(); right++) {
        sum += nums[right];
        while (sum >= target) {
            k = right - left + 1;
            res = res > k ? k : res;  // 题目要求是最小的长度，这个k不一定最小，暂时保存一下
            sum -= nums[left];
            left++;  // 动态滑窗！！窗口的大小不是固定的
        }
    }
    return res == 999999999 ? 0 : res;
}

int minSubQueueLen(int target, vector<int> nums) {
    // 滑窗size为k时
    for (int k = 1; k < nums.size() + 1; k++) {
        unordered_set<int> windowfalse;
        queue<int> window;
        for (int i = 0; i < nums.size(); i++) {
            window.push(nums[i]);
            if (i >= k) {
                // windowfalse.erase(nums[i - k]);  // 哈希映射会删除滑窗中的该元素。。
                window.pop();
            }
            int ans = 0;
            // cout << k << "滑窗";
            /*for (auto it = windowfalse.begin(); it != windowfalse.end(); it++)
            {
                int a = *it;
                ans += a;
            }*/
            // queue是没有遍历操作的，这是很弱智的做法，时间复杂度太高
            for (int i = 0; i < window.size(); i++) {  
                ans += window.front();
                window.push(window.front());
                window.pop();
            }
            if (ans >= target)
                return k;
        }
    }
    return 0;
}

int minSubvectorLen(int target, vector<int>& nums) {
    // 滑窗size为k时
    for (int k = 1; k < nums.size() + 1; k++) {
        vector<int> window;
        for (int i = 0; i < nums.size(); i++) {
            window.push_back(nums[i]);
            if (i >= k) {
                window.erase(window.begin());
            }
            int ans = 0;
            // 时间复杂度太高
            for (int i = 0; i < window.size(); i++) {
                ans += window[i];
            }
            if (ans >= target)
                return k;
        }
    }
    return 0;
}
// 超出时间限制。。双指针暴力解
int minSubArrayLen(int target, vector<int>& nums) {
    // 滑窗size为k时
    for (int k = 1; k < nums.size() + 1; k++) {
        int left = 0;
        for (int right = 0; right < nums.size(); right++) {
            if ((right - left) > (k - 1)) {
                left++;
            }
            int ansleft = left;
            int ansright = right;
            int ans = 0;
            while (ansleft <= ansright) {
                ans += nums[ansleft]; 
                ansleft++;
            }
            if (ans >= target) {
                return k;
            }
        }
    }
    return 0;
}