Li Kou brush question 02 (sum of three numbers + sum of maximum subsequence + nearest common ancestor of binary tree)

Sum of three numbers

  The classic question of finding the sum of three numbers , An upgraded version of the sum of two , If the problem is violent, it will reach O(nnn) Time complexity of , In order to reduce the time complexity , We can use sorting plus double pointers , First sort the array , Set the first element to be determined from the first number, and then set two double pointers ,l and r,l One after the first element Bit starts traversing ,r Start with the last one , If greater than negative undetermined element , be r Move right , whereas l Moving to the left , Know that two pointers meet , If equal Then add it to the answer array .

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

---

The largest subsequence and

  Written in dynamic programming

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int Max=nums[0];//Max The initial value is the first element 
        int sum=nums[0];//sum Values are update and Max The value of comparison 
        for(int i=1;i<nums.size();i++){
            if(i>0&&sum<0){// If sum<0 Remove the previous value , Replace sum Current value 
                sum=nums[i];
                Max=max(Max,sum);
            }
            else if(i>0){// If sum value >0 Add to the current value , And with Max Value comparison 
                sum+=nums[i];
                Max=max(Max,sum);
            }
            cout<<sum<<endl;
        }
        return Max;
    }
};

---

The best time to buy and sell stocks

Although the change is marked with a simple label , But I will do it after reading the solution T-T, You can get the answer in one traverse .

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int Min=1e9;// It is the lowest price of the stock 
        int Max=0;// Note that this is not the highest price of the stock , It is the highest profit at present 
        for(int i=0;i<prices.size();i++){// Traverse the exchange value once 
           Min=min(Min,prices[i]);
           Max=max(Max,prices[i]-Min);
        }
        return Max;
    }
};

---

The nearest common ancestor of a binary tree

class Solution {
public:
    TreeNode* ans;
    bool dfs(TreeNode* root,TreeNode* p,TreeNode* q){
        if(root==NULL){
            return false;// If you search all the way to the empty node , It means there is no p,q Two nodes , return false
        }
        bool t1=dfs(root->left,p,q);// Search left subtree 
        bool t2=dfs(root->right,p,q);// Search right subtree 
        if ((t1 && t2) || ((root->val == p->val || root->val == q->val) && (t1 || t2))) {
           //t1 and t2 Both are true or the current node is p or q Node and t1 or t2 If one is true, the answer will be the current node           
           ans = root;
        }
        return t1||t2||root->val==p->val||root->val==q->val;// Current traversal to p or q Node time , return true
    } 
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==NULL){
            return ans;
        }// Special judgement root When the root is empty 
        dfs(root,p,q);// Search for 
        return ans;                                 
    }
};