16. 最接近的三数之和

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

输入：nums = [-1,2,1,-4], target = 1 输出：2 解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

暴力枚举

class Solution { public: int threeSumClosest(vector<int>& nums, int target) { pair<int,int> res={1e4,0}; int n=nums.size(); sort(nums.begin(),nums.end()); for(int i=0;i<n;i++){ if(i && nums[i-1]==nums[i]) continue; for(int j=i+1;j<n;j++){ if(j>i+1 && nums[j]==nums[j-1]) continue; for(int k=j+1;k<n;k++){ if(abs(nums[i]+nums[j]+nums[k]-target)<res.first) res={abs(nums[i]+nums[j]+nums[k]-target),nums[i]+nums[j]+nums[k]}; } } } return res.second; } };

双指针

算法描述用双指针找到第一个 k 使得三元素之和等于target 那么k+1必定大于等于target 分别和去更新结果即可 class Solution { public: int threeSumClosest(vector<int>& nums, int target) { int n=nums.size(); pair<int,int> res(INT_MAX,INT_MAX); sort(nums.begin(),nums.end()); for(int i=0;i<n;i++){ for(int j=i+1,k=n-1;j<k;j++){ while(j<k-1 && nums[i]+nums[j]+nums[k-1]>=target) k--; int s=nums[i]+nums[j]+nums[k]; res=min(res,make_pair(abs(s-target),s)); if(j<k-1){ s=nums[i]+nums[j]+nums[k-1]; res=min(res,make_pair(target-s,s)); } } } return res.second; } };

17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

输入：“23” 输出：[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].

dfs

class Solution { public: unordered_map<char,string> map={ {'2',"abc"},{'3',"def"},{'4',"ghi"}, {'5',"jkl"},{'6',"mno"},{'7',"pqrs"}, {'8',"tuv"},{'9',"wxyz"} }; vector<string> res; void dfs(string& s,string& path,int idx){ if(idx==s.size()){ res.push_back(path); return; } for(int i=0;i<map[s[idx]].size();i++){ path.push_back(map[s[idx]][i]); dfs(s,path,idx+1); path.pop_back(); } } vector<string> letterCombinations(string digits) { if(!digits.size()) return res; string path; dfs(digits,path,0); return res; } };

更精简的dfs

class Solution { public: unordered_map<char,string> map={ {'2',"abc"},{'3',"def"},{'4',"ghi"}, {'5',"jkl"},{'6',"mno"},{'7',"pqrs"}, {'8',"tuv"},{'9',"wxyz"} }; vector<string> res; void dfs(string& s,string path,int idx){ if(idx==s.size()) res.push_back(path); else{ for(char& c:map[s[idx]]) dfs(s,path+c,idx+1); } } vector<string> letterCombinations(string digits) { if(!digits.size()) return res; dfs(digits,"",0); return res; } };

18. 四数之和

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。 注意： 答案中不可以包含重复的四元组。

给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。 满足要求的四元组集合为： [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]

class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { vector<vector<int>> res; int n=nums.size(); sort(nums.begin(),nums.end()); for(int i=0;i<n;i++){ if(i && nums[i]==nums[i-1]) continue; for(int j=i+1;j<n;j++){ if(j>i+1 && nums[j]==nums[j-1]) continue; for(int k=j+1,m=n-1;k<m;k++){ if(k>j+1 && nums[k]==nums[k-1]) continue; while(k<m-1 && nums[i]+nums[j]+nums[k]+nums[m]>target) m--; if(nums[i]+nums[j]+nums[k]+nums[m]==target) res.push_back({nums[i],nums[j],nums[k],nums[m]}); } } } return res; } };

19. 删除链表的倒数第N个节点

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后，链表变为 1->2->3->5.

最初版本

class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { int idx=0; ListNode* tmp=head; for(auto p=tmp;p;p=p->next) idx++; n=idx-n; if(n==0) return head->next; while(--n) tmp=tmp->next; tmp->next=tmp->next->next; return head; } };

虚拟头节点

class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* tmp=new ListNode(-1); tmp->next=head; int idx=0; for(auto p=tmp;p;p=p->next) idx++; auto p=tmp; for(int i=0;i<idx-n-1;i++) p=p->next; p->next=p->next->next; return tmp->next; } };

20. 有效的括号

给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串，判断字符串是否有效。 有效字符串需满足： 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。

输入: “()” 输出: true

栈

class Solution { public: bool isValid(string s) { unordered_map<char,char> map={ {'(',')'},{'{','}'},{'[',']'} }; stack<char> st; for(auto c:s){ if(st.empty() || map[st.top()]!=c) st.push(c); else st.pop(); } return st.empty(); } };