力扣刷题02（三数之和+最大子序和+二叉树最近公共祖先）

 经典的求三数之和的题目，两数之和的升级版，该题如果用暴力的话会达到O(nnn)的时间复杂度，为了减少时间复杂度，我们可以用排序加双指针的方法， 先将数组排序一遍，从第一个数开始设为待定的第一个元素再设置两个双指针，l和r，l从第一个元素后面一 位开始遍历，r从最后一位开始，若大于负待定元素，则r向右移，反之则l向左移，知道两指针相遇，若相等 则加入答案数组中。

class Solution {
public:
    vector> threeSum(vector& nums) {
        vector>ans;
        if(nums.size()<3){
            return ans;
        }
        sort(nums.begin(),nums.end());
        for(int i=0;i0&&nums[i]==nums[i-1]) continue;
            int p=nums[i];
            for(int l=i+1,r=nums.size()-1;li+1&&nums[l]==nums[l-1]) continue;
            
                while(l0){
                    r--;
                }
                if(l==r) break;
                 if(nums[l]+nums[r]+p==0){
                    ans.push_back({nums[l],nums[r],p});
                }
            }
        }
        return ans;
    }
};

 用动态规划写的

class Solution {
public:
    int maxSubArray(vector& nums) {
        int Max=nums[0];//Max初始值为第一个元素
        int sum=nums[0];//sum值为更新与Max比较的值
        for(int i=1;i0&&sum<0){//如果sum<0去掉之前的值，替换sum为当前值
                sum=nums[i];
                Max=max(Max,sum);
            }
            else if(i>0){//如果sum值>0与当前值相加，并且与Max值比较
                sum+=nums[i];
                Max=max(Max,sum);
            }
            cout< 

买卖股票的最佳时机 
 
改题虽然标的是简单标签，但还是看了题解才会做的T-T，一次遍历即可得出答案。
 
class Solution {
public:
    int maxProfit(vector& prices) {
        int Min=1e9;//为股票最低价
        int Max=0;//注意这里不是股票最高价，是目前得到的最高利润
        for(int i=0;i 
 

二叉树的最近公共祖先 
 
 
class Solution {
public:
    TreeNode* ans;
    bool dfs(TreeNode* root,TreeNode* p,TreeNode* q){
        if(root==NULL){
            return false;//如果一直搜索到空节点，则说明没有出现p，q两个节点，返回false
        }
        bool t1=dfs(root->left,p,q);//搜索左子树
        bool t2=dfs(root->right,p,q);//搜索右子树
        if ((t1 && t2) || ((root->val == p->val || root->val == q->val) && (t1 || t2))) {
           //t1和t2都为真或者当前节点为p或q节点且t1或t2有一个为真则使答案为当前节点          
           ans = root;
        }
        return t1||t2||root->val==p->val||root->val==q->val;//当前遍历到p或q节点时，返回true
    } 
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==NULL){
            return ans;
        }//特判root根为空的情况
        dfs(root,p,q);//搜索
        return ans;                                 
    }
};