LeetCode 2021.7.13.

专题：array数组

LeetCode 2021.7.13.

1、Two Sum两数之和

在这里插入图片描述

方法一：暴力枚举

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        for(int i=0;i<nums.size()-1;i++){
            for(int j=i+1;j<nums.size();j++){
                if(nums[i]+nums[j]==target) return {i,j};
            }
        }
        return {};
    }
};

复杂度分析：

时间复杂度：O(N^2)，其中 N 是数组中的元素数量。最坏情况下数组中任意两个数都要被匹配一次。
空间复杂度：O(1)。

方法二：哈希表

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {  //哈希表key:列表里的数字 value:例表里数字的下标
        unordered_map<int, int> hashtable;  //#include <unordered_map>
        for (int i = 0; i < nums.size(); ++i) {
            auto it = hashtable.find(target - nums[i]);  // 如果key存在，则find返回key对应的迭代器，如果key不存在，则find返回unordered_map::end
            if (it != hashtable.end()) {  // end()并没有指向一个元素，或者可以说是指向一个空的位置，即end()函数返回的不是指向最后一个元素的迭代器，而是指向最后一个元素后面的位置的迭代器。
                return {it->second, i};  // (*it).first会得到key，(*it).second会得到value。这等同于it->first和it->second。
            }
            hashtable[nums[i]] = i;
        }
        return {};
    }
};

复杂度分析

时间复杂度：O(N)，其中 N 是数组中的元素数量。对于每一个元素 x，我们可以 O(1) 地寻找 target - x。
空间复杂度：O(N)，其中 N 是数组中的元素数量。主要为哈希表的开销。

c++ map与unordered_map区别及使用
https://blog.csdn.net/qq_21997625/article/details/84672775.
重点：
1、map具有有序性，这是map结构最大的优点，其元素的有序性在很多应用中都会简化很多的操作，对于那些有顺序要求的问题，用map会更高效一些。
2、unordered_map因为内部实现了哈希表，因此其查找速度非常的快，但缺点是哈希表的建立比较耗费时间。对于查找问题，unordered_map会更加高效一些，因此遇到查找问题，常会考虑一下用unordered_map。
3、unordered_map的用法和map是一样的，提供了 insert，size，count等操作，并且里面的元素也是以pair类型来存贮的。

4、Median of Two Sorted Arrays寻找两个正序数组的中位数

在这里插入图片描述

方法一：归并取中位数
使用归并的方式，合并两个有序数组，得到一个大的有序数组。大的有序数组的中间位置的元素，即为中位数。

复杂度分析：

时间复杂度：O(m+n)
空间复杂度：O(m+n)

方法二：vector合并排序，取中位数

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        for(int i=0;i<nums2.size();i++){
            nums1.push_back(nums2[i]);
        }
        sort(nums1.begin(),nums1.end());
        if(nums1.size()%2==1){
            return nums1[nums1.size()/2];
        }
        else if(nums1.size()%2==0){
            return (nums1[nums1.size()/2]+nums1[nums1.size()/2-1])/2.0;
        }
        return NULL;
    }
};

复杂度分析：

时间复杂度：取决于sort？
空间复杂度：O(n)

方法三：双指针
不需要合并两个有序数组，只要找到中位数的位置即可。由于两个数组的长度已知，因此中位数对应的两个数组的下标之和也是已知的。维护两个指针，初始时分别指向两个数组的下标 00 的位置，每次将指向较小值的指针后移一位（如果一个指针已经到达数组末尾，则只需要移动另一个数组的指针），直到到达中位数的位置。

复杂度分析：

时间复杂度：O(m+n)
空间复杂度：O(1)

方法四：二分查找
题目要求最好要把时间复杂度降低到 O(log(m+n))，如果对时间复杂度的要求有 log，通常都需要用到二分查找。

暂未弄懂

复杂度分析：

时间复杂度：O(log(m+n))，其中 mm 和 nn 分别是数组nums 1和nums 2 的长度。初始时有 k=(m+n)/2或 k=(m+n)/2+1，每一轮循环可以将查找范围减少一半，因此时间复杂度是O(log(m+n))。
空间复杂度：O(1)

11、Container With Most Water盛最多水的容器

在这里插入图片描述
方法一：暴力枚举（超时）

class Solution {
public:
    int maxArea(vector<int>& height) {
        int max=0,min=0;
        for(int i=0;i<height.size()-1;i++){
            for(int j=i+1;j<height.size();j++){
                if(height[i]>height[j]) min=height[j];
                else min=height[i];
                if(min*(j-i)>max) max=min*(j-i);
            }
        }
        return max;
    }
};

复杂度分析：

时间复杂度：O(N^2)
空间复杂度：O(1)

方法二：双指针法

像这种两头的，有可能使用双指针法，问题就在于怎么移动双指针。
解题思路：看官方视频

class Solution {
public:
    int min(int a,int b){
        if(a<b) return a;
        else return b;
    }

    int maxArea(vector<int>& height) {
        int max=0;
        int i=0,j=height.size()-1;
        while(i<j){
            if(max<((j-i)*min(height[i],height[j]))) max=(j-i)*min(height[i],height[j]);
            if(height[i]<height[j]) i++;
            else j--;
        }
        return max;
    }
};