《LeetCode》查找

怼烎@ 2023-02-27 10:35 12阅读 0赞

**1、container-with-most-water**

**题目描述：**给定n个非负整数a1，a2，…，an，其中每个数字表示坐标(i, ai)处的一个点。以（i，ai）和（i，0）（i=1,2,3...n）为端点画出n条直线。你可以从中选择两条线与x轴一起构成一个容器，最大的容器能装多少水？  
注意：你不能倾斜容器

![format_png][]

class Solution {
    public:
        /**
         * 
         * @param height int整型vector 
         * @return int整型
         */
        const int Max(const int &l1,const int &l2) {return l1>l2?l1:l2;}
        const int Min(const int &l1,const int &l2) {return l1<l2?l1:l2;}
        int maxArea(vector<int>& height)
        {
            int len=height.size()-1;
            int i=0,j=len,res=0;
            int Lmax=height[0],Rmax=height[len];
            while(i<j)
            {
                res=Max(res,Min(Lmax,Rmax)*(j-i));
                if(Lmax<=Rmax)
                    Lmax=height[++i];
                else
                    Rmax=height[--j];
            }
            return res;
        }
    };

**2、3sum**

**题目描述**：给出一个有n个元素的数组S，S中是否有元素a,b,c满足a+b+c=0？找出数组S中所有满足条件的三元组。

注意：

1.  三元组（a、b、c、d）中的元素必须按非降序排列。（即a≤b≤c）
2.  解集中不能包含重复的三元组。

class Solution {
    public:
        //先排序，再夹逼
        vector<vector<int> > threeSum(vector<int> &num) {
            vector<vector<int> > result;
            int len = num.size();
            if(len<3) return result;
            sort(num.begin(), num.end());
             
            vector<int> tmp(3);
            for(int i=0; i<len; i++){
                //防止重复,防止与之前的重复
                if(i == 0 || num[i] != num[i-1]){
                    int left = i+1;
                    int right = len-1;
                    while(left < right){
                        while(left<right && num[i] + num[left] + num[right] > 0) right--;
                         if(left<right && num[i] + num[left] + num[right] == 0){
                            tmp[0] = num[i];
                            tmp[1] = num[left];
                            tmp[2] = num[right];
                            result.push_back(tmp);
                             while(left<right && num[left] == tmp[1]) left++;   //很关键，可以排除之后的重复
                        }else left++;
                    }
                     
                }
            }
            return result;
        }
    };

[format_png]: /images/20230209/12d9e1ebd74c482da3ac29ef9031ae3f.png