● 977. 有序数组的平方

● 自己看到题目的第一想法

首先求平方然后排序，时间复杂度取决于快排的时间复杂度O(logn)

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {//第一个想法 直接平方 然后排序
        for(int i =0;i<nums.size();i++){
            int a =nums[i]*nums[i];
            nums[i] = a;
        }
        Quicksort(nums, 0, nums.size()- 1);
        return nums;
    }

    void Quicksort(vector<int>& r, int low, int hight)
    {
        int mid;
        if (low < hight)
        {
            mid = part(r, low, hight);  // 返回基准元素位置
            Quicksort(r, low, mid - 1); // 左区间递归快速排序
            Quicksort(r, mid+1, hight); // 右区间递归快速排序
        }
    }

private:
    int part(vector<int>& r, int low, int hight)  //划分函数
    {
        int i = low, j = hight, pivot = r[low]; 
        while (i < j){
            while (i<j && r[j]>pivot) {
                j--;
            }
            if (i < j){
                swap(r[i++], r[j]);  //r[i]和r[j]交换后 i 向右移动一位
            }
            while (i < j && r[i] <= pivot){
                i++;
            }
            if (i < j){
                swap(r[i], r[j--]);  //r[i]和r[j]交换后 i 向左移动一位
            }
        }
        return i;  //返回最终划分完成后基准元素所在的位置
    }
};

调用已有的函数实现快速排序

 vector<int> sortedSquares(vector<int>& nums) {
        for(int i =0;i<nums.size();i++){
            int a =nums[i]*nums[i];
            nums[i] = a;
        }
        sort(nums.begin(), nums.end()); // 快速排序
        return nums;
    }

● 看完代码随想录之后的想法

相向的双指针

    vector<int> sortedSquares(vector<int>& nums) {
        //新数组和新下标
        vector<int> a(nums.size());
        int m=0;//新数组的索引可以初始化为m=nums.size()-1,更新的时候m--
        
        int left =0,right= nums.size()-1;
        while(left<=right){//可以等号
            if(nums[left]*nums[left]>nums[right]*nums[right]){
                a[nums.size()-1-m]=nums[left]*nums[left];//使用这种方法时是否减1很纠结
                left++;
                m++;
            }
            else{
                a[nums.size()-1-m]=nums[right]*nums[right];
                right--;
                m++;
            }
        }
        return a;
    }

209. 长度最小的子数组

● 自己看到题目的第一想法

双指针：方向相同的双指针可以用来求整数数组中子数组的和或乘积，p1和p2都指向数组的第一个数字，若两指针之间的子数组之和大于目标值，右移p1删除子数组左端数字；若两指针之间的子数组之和小于目标值，右移p2在子数组右端增加数字。
虽然有两层循环，但时间复杂度 不是O(n^2)， 主要是看每一个元素被操作的次数，每个元素在滑动窗后进来操作一次，出去操作一次，每个元素都是被操作两次，所以时间复杂度是 2 × n 也就是O(n)。

    int minSubArrayLen(int target, vector<int>& nums) {
    int left=0,right=0;
    int sum=0;
    int minlen = INT_MAX;
    while(right<nums.size()){
        sum+=nums[right];
        while(sum>=target){
            int len = right-left+1;
            minlen=min(minlen,len);
            sum-= nums[left];
            left++;
        }
        right++;//忘记这句了 如果是for循环就可以避免这种情况
    }
    return minlen==INT_MAX?0:minlen;//题目要求：如果不存在符合条件的子数组，返回 0
    }

方法二为暴力解法，会超出时间限制，枚举所有子数组并找出符合条件的。

相关题目搜索

904. 水果成篮

使用哈希表， 将水果的种类作为key，出现的次数作为value。在哈希表中一样的元素在同一个位置上累计数量 cnt.size()只能等于2，当其大于2时，说明窗口左边界该缩小了。

    int totalFruit(vector<int>& fruits) {
        unordered_map<int, int> cnt;
        int left = 0;//left和right分别是窗口的左右边界
        int maxlen = 0;
        for (int right = 0; right < fruits.size(); right++) {
            cnt[fruits[right]]++;
            while (cnt.size() > 2) {
                auto it = cnt.find(fruits[left]);//查找key为fruits[left]的键值对是否存在 
                (it->second)--;//出现次数减1
                if (it->second == 0) {//从哈希表中删除
                    cnt.erase(it);
                }
                left++;
            }
            maxlen = max(maxlen, right - left + 1);
        }
        return maxlen;
    }

76. 最小覆盖子串

在处理滑动窗口求最大.../最小...时，总是执着于找到那个最值，但实际上无须找到最值，你只需要找到所有满足条件的可能的情况，记录他的长度/乘积等等，然后再求一个最值。

string minWindow(string s, string t) {
        unordered_map<char, int> hs, ht;//两个哈希表字符串s的和字符串t的
        for (auto c:t){
            ht[c] ++ ;
        } 
        string res;//s中包含t的最小子串
        int cnt = 0;
        int left =0;//滑动窗口的左右边界
        for (int right = 0; right <s.size(); right++ ) {
            hs[s[right]] ++ ;
            if (hs[s[right]] <= ht[s[right]]){
//说明当前新加入的字符s[right]是必需的，且还未到达字符串t所要求的数量
                cnt ++ ;
            }
            while (hs[s[left]] > ht[s[left]]){//说明左边界的元素多了 窗口再小点
                hs[s[left ++ ]] -- ;
            } 
            if (cnt == t.size()) {//说明此时滑动窗口包含符串 t 的全部字符
                if (res.empty() || right - left + 1 < res.size()){//现在的这个比原来的子串更短
                    res = s.substr(left, right - left + 1);
                }
            }
        }
        return res;
    }

59. 螺旋矩阵 II

    vector<vector<int>> generateMatrix(int n) {
        int num = 1;
        int left = 0, top = 0, right = n - 1, bottom = n - 1;//起始边界与终止边界
        vector<vector<int>> res(n,vector<int>(n));//返回的结果是二维数组
        //写成了 vector<vector<int>> ret(n,vector<int>);
        while (num <= n*n ) {//落了一个大循环
            //left to right
            for (int i = left; i <= right; ++i){
                res[top][i] = num++;
            }
            ++top;
            //top to bottom
            for (int i = top; i <= bottom; ++i){
                 res[i][right] = num++;//写成了ret[right][i]=num++;
            }
            --right;
            //right to left
            for (int i = right; i >= left; --i){
                 res[bottom][i] = num++;//写成了ret[i][bottom]=num++;
            }
            --bottom;
            //bottom to top
            for (int i = bottom; i >= top; --i){
                 res[i][left] = num++;//写成了ret[left][j]=num++;
            }
            ++left;
        }
        return res;
    }

相关题目搜索

54. 螺旋矩阵

这道题和下面这道一模一样

剑指 Offer 29. 顺时针打印矩阵

在原来代码上改的，错误原因是这不是方阵而是矩阵，行列大小是不相同的

vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int num = 1;
        int n = matrix[0].size();
        int left = 0, top = 0, right = n - 1, bottom = n - 1;//起始边界与终止边界
        vector<int>res;
        while (num <= n*n) {
            //left to right
            for (int i = left; i <= right; ++i){
                res.push_back(matrix[top][i]);
                num++;
            }
            ++top;
            //top to bottom
            for (int i = top; i <= bottom; ++i){
                 res.push_back(matrix[i][right]);
                 num++;
            }
            --right;
            //right to left
            for (int i = right; i >= left; --i){
                 res.push_back(matrix[bottom][i]);
                 num++;
            }
            --bottom;
            //bottom to top
            for (int i = bottom; i >= top; --i){
                 res.push_back(matrix[i][left]);
                 num++;
            }
            ++left;
        }
        return res;
    }

矩阵的写法

 vector<int> spiralOrder(vector<vector<int>>& matrix) {
        if (matrix.empty()) 
            return {};
        int left = 0, top = 0, right = matrix[0].size() - 1, bottom = matrix.size() - 1;
        vector<int>res;
        while (true){
            //left to right
            for (int i = left; i <= right; ++i){
                res.push_back(matrix[top][i]);
            }
            ++top;
            if (top > bottom) 
                break;
            //top to bottom
            for (int i = top; i <= bottom; ++i){
                 res.push_back(matrix[i][right]); 
            }
            --right;
            if (right < left) 
                break;
            //right to left
            for (int i = right; i >= left; --i){
                 res.push_back(matrix[bottom][i]);    
            }
            --bottom;
            if (bottom < top) 
                break;
            //bottom to top
            for (int i = bottom; i >= top; --i){
                 res.push_back(matrix[i][left]);
            }
            ++left;
            if (left > right) 
                break;
        }
        return res;
    }