数组

240.搜索二位矩阵II

解法1：直接遍历搜索。每行每行进行搜索，当该行中碰到比target大的数，那么遍历下一行的时候就不要再访问这一列了。
时间复杂度：O(m*n);
代码如下：

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(); //可以访问的行数
        int n = matrix[0].size(); //可以访问的列数
        for(int i=0;i<m;++i){
            for(int j=0;j<n;++j){
                if(matrix[i][j]==target)
                return true;
                else if(matrix[i][j]>target){
                    n = j;  //更新可以访问的列数，减少遍历没必要的次数。
                    break;
                }
                else
                continue;
            }
        }
        return false;
    }
};

解法2：根据题意我们知道该矩阵每行每列元素之间都是升序的，然后题目又是要求搜索，我们第一反应应该是二分法搜索。所以可以采用二分法进行遍历每一行。

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(); //行
        int n = matrix[0].size(); //列
        int left = 0, right = n-1;
        for(int i=0;i<m;++i){
            left = 0;
            right = n-1;
            while(right>=left){
                int mid = (left+right)>>1;
                if(matrix[i][mid]==target)
                return true;
                else if(matrix[i][mid]<target)
                    left = mid + 1;
                else{
                    n = mid; //这里由于matrix[i][mid]大于target了，由于列也是递增的所以把下次遍历的列更新一下，避免没必要的遍历
                    right = mid-1;
                }
            }
        }
        return false;
    }
};

435.无重叠区间

解法1：动态规划。与我写的第一篇博客dp定义是非常类似的：最长递增子序列。
首先我们对区间进行排序，然后利用动态规划解题。
dp数组表示前i个区间里最多区间数（dp数组中元素初始化为1）。
状态转移方程：
代码如下：

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if(intervals.size()<=1)
        return 0;
        sort(intervals.begin(),intervals.end());
        vector<int> dp(intervals.size()+1,1); //设置一个dp数组用来描述前i个区间的最大个数区间
        for(int i=1;i<intervals.size();++i)
        {
            for(int j=0;j<i;++j){
                if(intervals[j][1]<=intervals[i][0]&&dp[i]<dp[j]+1){
                    dp[i] = dp[j] + 1;
                }
            }
            dp[intervals.size()] = max(dp[i],dp[intervals.size()]);
        }
        return intervals.size() - dp[intervals.size()];
    }
};

时间复杂度O(n^2)；
解法2：贪心。
我们先对区间右端点进行排序，从小到大进行排序。然后再联想安排会议的问题，就是在一天之中安排会议次数最多的题目。贪心策略是，区间结束早的先安排，因为这样后面才有可能安排到更多的会议次数。再回到这题，排好序后，让intervals[i][0]比前一个优解（i前面的intervals[j][1]，满足条件的最小intervals[k][1]）比较，然后产生新的最优解。

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if(intervals.size()<=1)
        return 0;
        sort(intervals.begin(),intervals.end(),[](auto &a,auto &b)->bool{return a[1]<b[1];});
        int ans = 1; //包括自身区间，所以初始化为1
        int left = intervals[0][1];
        for(int i=1;i<intervals.size();++i){
            if(intervals[i][0]>=left){
                ++ans;
                left = intervals[i][1];
            }
        }
        return intervals.size() - ans;
    }
};

时间复杂度：O(n*logn)；

334.递增的三元子序列

解法1：利用额外两数组进行辅助解题。用一个minArray表示i之前最小的元素，用一个maxArray表示j之后最大的元素。然后循环对对应的minArray和maxArray中的元素比较，如果大于minarray小于maxarray那么就存在递增的三元子序列.

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        if(nums.size()<3)
        return false;
        int n = nums.size();
        vector<int> minArray(n);//表示i之前最小的元素
        minArray[0] = nums[0];
        for(int i=1;i<n;++i)
        minArray[i] = min(minArray[i-1],nums[i]);

        vector<int> maxArray(n);//表示j之后最大的元素
        maxArray[n-1] = nums[n-1];
        for(int j=n-2;j>=0;--j)
        maxArray[j] = max(maxArray[j+1],nums[j]);

        for(int i=1;i<n;++i){
            if(nums[i]>minArray[i]&&nums[i]<maxArray[i])
            return true;
        }
        return false;
    }
};

解法2：贪心。第一反应我想到那个“股票最大利润”那题，也是用贪心，也是不断更换最小值产生最优解，先初始化leftnum=nums[0]与midnum=无穷，每次与leftnum比较，如果比它小就更换leftnum，比它大就和midnum比较，如果大就存在递增三元子序列，不是的话就更换midnum。

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        if(nums.size()<3)
        return false;
        int n = nums.size();
        int minNum = nums[0];
        int midNum = pow(2,31) - 1;
        for(int i=1;i<n;++i){
            if(nums[i]>midNum)
            return true;
            else if(nums[i]<=minNum) //这里等号不可以去掉，防止后面midNum和minNum相等
            minNum = nums[i];
            else
            midNum = nums[i];
        }
        return false;
    }
};

238.除自身以外数组的乘积

解法1：利用空间换时间的想法，建立两个数组nums1，nums2，让nums1里的元素表示i前的元素乘积，让nums2里的元素表示i后的元素乘积。
则除自身以外数组的乘积就为：nums1[i-1]*nums2[i+1];(i>0&&i<n-1)。
代码如下：

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        if(n<=1)
        return nums;
        vector<int> nums1(nums); //存取nums前i项元素的乘积
        for(int i=1;i<n;++i)
        nums1[i] *= nums1[i-1];

        vector<int> nums2(nums); //存取nums后n-i项元素的乘积
        for(int i=n-2;i>=0;--i)
        nums2[i] *= nums2[i+1];

        nums[0] = nums2[1];  //索引0后所有元素的乘积
        nums[n-1] = nums1[n-2];  //索引n-1前所有元素的乘积
        for(int i=1;i<n-1;++i)
        nums[i] = nums1[i-1]*nums2[i+1];

        return nums;
    }
};

时间复杂度：O(n);
空间复杂度：O(n);

560.和为k的子数组

解法1：枚举。以start为索引遍历，在start索引连续性往前有连续数组元素和为k则满足的子数组数加1，最后返回满足的子数组数目。
时间复杂度：O(N^2);空间复杂度：O(1)；
代码如下：

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int count = 0;
        for(int start = 0;start<nums.size();++start){
            int sum = 0;
            for(int end = start;end>=0;--end){
                sum += nums[end];  //end索引前的连续子数组和
                if(sum==k)
                ++count;
            }
        }
        return count;
    }
};

解法2：计算前缀和再利用哈希表查找。我们知道前缀和计算 pre[i] = nums[i-1] + pre[i-1]；
那么求[i,j]的序列和则 pre[j] - pre[i-1]；我们要求和为k的子数组，就是求序列为[i,j]的序列和，也就是pre[j] - pre[i-1] = k；交换一下：pre[i-1] = pre[j] - k; 所以我们可以利用哈希表，找key为pre[j]-k，value为pre[i-1]出现的次数。pre[i-1]表示前索引i的元素和。考虑存在pre[j]==k的情况，所以应该提前存入key：0，value：1的数据。
代码如下：

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int,int> mp;
        mp[0] = 1;
        int count = 0;
        int pre = 0;
        for(int i=0;i<nums.size();++i){
            pre += nums[i];
            if(mp.find(pre-k)!=mp.end())
            count += mp[pre-k];
            ++mp[pre];
        }
        return count;
    }
};