给你n个非负整数a1，a2，...，an，每个数代表坐标中的一个点(i, ai)。在坐标内画n条垂直线，垂直线i的两个端点分别为(i, ai)和(i, 0)。找出其中的两条线，使得它们与x轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器。
分析: 任意选择两点，area=min(ai,aj)*(j-i)，找最大area；
class Solution {
public:
int maxArea(vector<int>& height) {
//双指针，从左右两边向中间移动，每次移动高度较低的那侧对应指针，要求下一个指针位置比原来的高度高,如果没有发现，则直接返回当前已找到的最大area
int str1=0,str2=height.size()-1;
int maxAr=0,area=0;
while(str1<str2)
{
area=(std::min(height[str1],height[str2]))*(str2-str1);
if(area>maxAr)
maxAr=area;
if(height[str1]>height[str2])
{
str2--;
for(int j=str2;j>str1;j--)
{
if(height[j]>height[str2+1])
{
str2=j;
break;
}
if(j==str1) return maxAr;
}
}else{
str1++;
for(int j=str1;j<str2;j++)
{
if(height[j]>height[str1-1])
{
str1=j;
break;
}
if(j==str2) return maxAr;
}
}
}
return maxAr;
}
};
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串""。
分析：遍历每个字符串，以首个字符串作为对照，当首字符串不是对应字符串的字串时，字串从右往左减一个，直到所有字符串遍历完。
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if(strs.empty())return "";
//if(strs.size()==1)return strs[0];
string res=strs[0];
int j=res.length();
for(string s:strs)
{
while(s.find(res)!=0)res=res.substr(0,j--);
}
return res;
}
};
给你一个包含n个整数的数组nums，判断nums中是否存在三个元素a，b，c ，使得a + b + c = 0 ？请你找出所有和为0且不重复的三元组。
注意：答案中不可以包含重复的三元组。
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
//排序+双指针
vector<vector<int>>res;
if(nums.empty()||nums.size()<3)return res;
sort(nums.begin(),nums.end());
int n=nums.size();
for(int i=0;i<n-2;i++)
{
if(i>=1&&nums[i]==nums[i-1]) //如果第一个元素有重复元素跳过
continue;
int j=i+1;
int k=n-1;
int target=0-nums[i];
while(j<k&&j>i&&k<n)
{
if(nums[j]+nums[k]>target)
{
k--;
}else if(nums[j]+nums[k]<target)
{
j++;
}else{
//如果第二个或者第三个有重复元素，跳过
res.push_back({nums[i],nums[j],nums[k]});
while(j+1<k&&nums[j]==nums[j+1])
{
j++;
}
while(k>j+1&&nums[k]==nums[k-1])
{
k--;
}
j++;k--;
}
}
}
return res;
}
};
