- 11 Container With Most Water
int maxArea(vector<int>& height) {}
题意：每个数字是一个隔板高度，数字的下标是隔板的位置，求哪两块隔板之间能够盛放最多的水。
思路：双指针法，哪个指针低哪个移动。
- 12 Integer to Roman
string intToRoman(int num) {}
将数字转化为罗马数字
思路：对于这种情况不多的，可以将所有情况全部罗列出来。
- 13 Roman to Integer
- 14 Longest Common Prefix
string longestCommonPrefix(vector<string>& strs) {}
思路：strs[0].find(tmp)
其实使用最朴素的想法就可以了
- 15 3Sum（3）
vector<vector<int>> threeSum(vector<int>& nums) {}
题意：找到所有和恰好等于零的三元组
思路：双指针法。注意可能存在相等的数字。
教训：这个题目看似简单，其中有许多耐人寻味的地方。双指针发的应用方式也是需要记住的东西。
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ret;
sort(nums.begin(), nums.end());
int size = nums.size();
for(int i = 0;i < size;){
int begin = i + 1, end = size - 1;
while(begin < end){
if(nums[begin] + nums[end] + nums[i] == 0){
ret.push_back({nums[begin++], nums[i], nums[end--]});
while(begin < end && nums[begin] == nums[begin - 1]) begin ++;
while(begin < end && nums[end] == nums[end + 1]) end --;
}else if(nums[begin] + nums[end] + nums[i] < 0){
begin ++;
while(begin < end && nums[begin] == nums[begin - 1]) begin ++;
}else{
end --;
while(begin < end && nums[end] == nums[end + 1]) end --;
}
}
++ i;
while(i < size && nums[i - 1] == nums[i]) ++i;
}
return ret;
}
};
- 16 3Sum Closest
int threeSumClosest(vector<int>& nums, int target) {}
题意：和最接近target的三元组
思路：双指针法。不用考虑相等的数字。
- 17 Letter Combinations of a Phone Number
vector<string> letterCombinations(string digits) {}
题意：给出数字组合，返回这个数字组合可能想要表达的字母组合（手机按键）
思路：回溯
- 18 4Sum
vector<vector<int>> fourSum(vector<int>& nums, int target) {}
思路：四指针法（将两个指针固定的双指针法）
- 19 Remove Nth Node From End of List
ListNode* removeNthFromEnd(ListNode* head, int n) {}
题意：删除倒数第n个节点
思路：双指针法
- 20 Valid Parentheses
bool isValid(string s) {}
思路：左括号压栈右括号，右括号出栈来比较
