1. 知识点总结

题目	难度	知识点
最长回文子串	🐸🐸	DP
盛水最多的容器	🐸🐸	剪枝（虽然严格来讲不是剪枝，但主要还是人为控制循环的复杂度）
三数之和	🐸🐸

2. 分题题解

2.1 最长回文子串

暴力解法会超时47/180

class Solution {
public:
string res;
int ans;
   bool isok(int left,int right,string s){
       int l=left;
       int r=right;
       //cout<<"?"<<s.substr(l,r-l+1)<<endl;
       while(left<=right){
           if(s[left]!=s[right]){
               return false;
           }else{
               left++;
               right--;
           }
       }
        if(r-l+1>ans){
            //cout<<"!"<<endl;
            res=s.substr(l,r-l+1);
            ans=r-l+1;
        }
       return true;
   }
    string longestPalindrome(string s) {
       int len=s.length();
       //寻找两个字符串之间的最大公共子串
        ans=0;
        if(len==0){
            return "";
        }else{
            res=s[0];
            for(int i=0;i<len;i++){
                for(int j=len-1;j>=i+ans;j--){
                    if(isok(i,j,s)){
                        break;
                    }
                }
            }
            return res;
        }

    }
};

正确解法：动态规划

考虑的状态转移方程（len>2）是dp[i][j]=dp[i+1][j-1]&&(s[i]==s[j])，注意在len<=2特判，dp[i][j]=(s[i]==s[j])

class Solution {
public:

    string longestPalindrome(string s) {
       int len=s.length();
       if(len==0){
           return "";
       }
       //动态规划解法
       vector<vector<bool> >isR(len);
       //初始化全为false
       for(int i=0;i<len;i++){
           isR[i].resize(len);
           fill(isR[i].begin(),isR[i].end(),false);
           isR[i][i]=true;
       }
       //状态转移方程
       string res="";
       res+=s[0];
       int ans=1;
       for(int L=2;L<=len;L++){
           //边界
           for(int i=0;i<=len-L;i++){
               int j=i+L-1;
               //需要考虑边界条件
               if(s[i]!=s[j]){
                   isR[i][j]=false;
               }else{
                   //相等
                   if(L<=2){
                       isR[i][j]=true;
                   }else{
                       isR[i][j]=isR[i+1][j-1];
                   }
               }
               if(isR[i][j]&&L>ans){
                   ans=L;
                   res=s.substr(i,L);
               }
           }
       }
        return res;
    }
};

2.2 成水最多的容器

还是卡时间，暴力51/63

class Solution {
public:
    int maxArea(vector<int>& height) {
        int ans=0;
        int len=height.size();
        //可以暴力
        for(int i=0;i<len-1;i++){
            for(int j=0;j<len;j++){
                int size=min(height[i],height[j])*(j-i);
                if(size>ans){
                    ans=size;
                }
            }
        }
        return ans;
    }
};

加上轻微的剪枝即可

class Solution {
public:
    int maxArea(vector<int>& height) {
        int ans=0;
        int len=height.size();
        
        for(int i=0;i<len-1;i++){//此处剪枝，注意height可能为0
            for(int j=i+ans/(max(1,height[i]));j<len;j++){
                int size=min(height[i],height[j])*(j-i);
                if(size>ans){
                    ans=size;
                }
            }
        }
        return ans;
    }
};

emm

2.3 三数之和

比较惨烈地通过了，算是暴力破解，（5% vs 4%）四舍五入过了≈没有过

class Solution {
public:

    vector<vector<int>> threeSum(vector<int>& nums) {
        //找出所有和为0的不重复的三元组
        int len=nums.size();
        vector<vector<int> >v;
        sort(nums.begin(),nums.end());
        map<int,int>pos;//某个数字的位置
        
        for(int i=0;i<len;i++){
            pos[nums[i]]=i;
        }
        for(int i=0;i<len-2;i++){
            if(i&&nums[i]==nums[i-1]){
                continue;
            }
            map<int,bool>vis;
            for(int j=i+1;j<len-1;j++){
                if(vis[nums[j]]){
                    continue;
                }else{
                    vis[nums[j]]=true;
                }
                if(pos.find(-nums[i]-nums[j])!=pos.end()){
                    if(pos[-nums[i]-nums[j]]>j){
                        //cout<<j<<" "<<pos[-nums[i]-nums[j]];
                        
                        v.push_back({nums[i],nums[j],-nums[i]-nums[j]});
                        
                    }
                }
            }
            
        }
        return v;
    }
};