依图凉凉经（送两道算法题）

第一道题目是二维有序矩阵查找特定target是否存在。二维有序矩阵是指每一行和每一列分别是递增的。
此题目的较优解法是每次比较剩余矩阵的右上角的元素key和target的关系，初始值row=0，col=nums[0].size()-1，target小于key时，key所在的列及右边列都比target打，故把col变量减一，target大于key时，key所在的行都比target小，故把row变量加一。直到row和col越界。返回false。（参考下图）
https://img-blog.csdn.net/20160324195705030

#include <bits/stdc++.h>
using namespace std;
bool isExists(vector<vector<int>> &nums, const int target) {
    int row = 0, col = nums[0].size()-1;
    while(row < nums.size() && col >= 0) {
        if(target == nums[row][col]) {
            return true;
        }else if(target < nums[row][col]) {
            col--;
        } else {
            row++;
        }
    }
    return false;
}
int main(){
    vector<vector<int>> v = {{1,2,3,4}, {2,3,4,5}, {3,4,5,6}, {4,5,6,7}};
    cout << to_string(isExists(v, 10)) << endl;
    cout << to_string(isExists(v, 7)) << endl;
    return 0;
}

第二题，求字符串中"YTTYYTYTYTYTT"Y和T的数量相等的最长字串，这道题目可以类比为经典题目：最长01字串的问题。不多废话了，直接上代码

#include <bits/stdc++.h>
using namespace std;
bool isExists(vector<vector<int>> &nums, const int target) {
    int row = 0, col = nums[0].size()-1;
    while(row < nums.size() && col >= 0) {
        if(target == nums[row][col]) {
            return true;
        }else if(target < nums[row][col]) {
            col--;
        } else {
            row++;
        }
    }
    return false;
}

int longest0_1(const vector<int> &nums){
    vector<int> part_sum;
    int sum = 0;
    for(int i = 0; i < nums.size(); i++) {
        sum += nums[i];
        part_sum.push_back(sum);
    }
    int ans = 0;
    map<int,int> mp;
    for(int i = 0; i < part_sum.size(); i++) {
        if(mp.count(part_sum[i]) == 0) {
            mp[part_sum[i]] = i;
        } else {
            ans = max(ans, i-mp[part_sum[i]]);
        }
    }
    return ans;
}
int main(){
    vector<int> v = {-1,-1,1,-1,1};
    cout << longest0_1(v) << endl;
    return 0;
}

PS:前两天感冒发烧状态太差，面试时这两道题都凉了。回来之后思考了一下题目，来回馈牛友。