（16）最接近的三数之和（中等）
实现思路：
本题与前文讲的三数之和有相同之处，但是本题求的是最接近的三数之和，所以我们这里可以使用键值对来映射对应的差值与值的关系，从而达到目的。
代码实现如下：
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
sort(nums.begin(),nums.end());
pair<int,int> res(INT_MAX,INT_MAX);
for(int i=0;i<nums.size();i++)
{
for(int j=i+1,k=nums.size()-1;j<k;j++)
{
while(k-1>j && 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(k-1>j)
{
s=nums[i]+nums[j]+nums[k-1];
res=min(res,make_pair(target-s,s));//pair比较的时候是先比较第一个参数，如果二者相同在比较第二个参数
}
}
}
return res.second;
}
};（17）电话号码的组合（中等）
实现思路：
对于这种排列组合的问题，我们最先想到的就是dfs，首先在这里引入一个例题（具体题目可以自Acwing上搜索排序数字）
eg、排列数字
题目描述：
给定一个整数 n，将数字 1∼n 排成一排，将会有很多种排列方法。
现在，请你按照字典序将所有的排列方法输出。
实现思路：
对于上述问题，我们可以这样进行排列：
假设有 3 个空位，从前往后填数字，每次填一个位置，填的数字不能和前面一样。
最开始的时候，三个空位都是空的：__ __ __
首先填写第一个空位，第一个空位可以填 1，填写后为：1 __ __
填好第一个空位，填第二个空位，第二个空位可以填 2，填写后为：1 2 __
填好第二个空位，填第三个空位，第三个空位可以填 3，填写后为： 1 2 3
这时候，空位填完，无法继续填数，所以这是一种方案，输出。
然后往后退一步，退到了状态：1 2 __ 。剩余第三个空位没有填数。第三个空位上除了填过的 3 ，没有其他数字可以填。
因此再往后退一步，退到了状态：1 __ __。第二个空位上除了填过的 2，还可以填 3。第二个空位上填写 3，填写后为：1 3 __
填好第二个空位，填第三个空位，第三个空位可以填 2，填写后为： 1 3 2
这时候，空位填完，无法继续填数，所以这是一种方案，输出。
然后往后退一步，退到了状态：1 3 __ 。剩余第三个空位没有填数。第三个空位上除了填过的 2，没有其他数字可以填。
因此再往后退一步，退到了状态：1 __ __。第二个空位上除了填过的 2，3，没有其他数字可以填。
因此再往后退一步，退到了状态：__ __ __。第一个空位上除了填过的 1，还可以填 2。第一个空位上填写 2，填写后为：2 __ __
填好第一个空位，填第二个空位，第二个空位可以填 1，填写后为：2 1 __
填好第二个空位，填第三个空位，第三个空位可以填 3，填写后为：2 1 3
这时候，空位填完，无法继续填数，所以这是一种方案，输出。
然后往后退一步，退到了状态：2 1 __ 。剩余第三个空位没有填数。第三个空位上除了填过的 3，没有其他数字可以填。
因此再往后退一步，退到了状态：2 __ __。第二个空位上除了填过的 1，还可以填 3。第二个空位上填写 3，填写后为：2 3 __
填好第二个空位，填第三个空位，第三个空位可以填 1，填写后为：2 3 1
这时候，空位填完，无法继续填数，所以这是一种方案，输出。
然后往后退一步，退到了状态：2 3 __ 。剩余第三个空位没有填数。第三个空位上除了填过的 1，没有其他数字可以填。
因此再往后退一步，退到了状态：2 __ __。第二个空位上除了填过的 1，3，没有其他数字可以填。
因此再往后退一步，退到了状态：__ __ __。第一个空位上除了填过的 1，2，还可以填 3。第一个空位上填写 3，填写后为：3 __ __
填好第一个空位，填第二个空位，第二个空位可以填 1，填写后为：3 1 __
填好第二个空位，填第三个空位，第三个空位可以填 2，填写后为：3 1 2
这时候，空位填完，无法继续填数，所以这是一种方案，输出。
然后往后退一步，退到了状态：3 1 __ 。剩余第三个空位没有填数。第三个空位上除了填过的 2，没有其他数字可以填。
因此再往后退一步，退到了状态：3 __ __。第二个空位上除了填过的 1，还可以填 2。第二个空位上填写 2，填写后为：3 2 __
填好第二个空位，填第三个空位，第三个空位可以填 1，填写后为：3 2 1
这时候，空位填完，无法继续填数，所以这是一种方案，输出。
然后往后退一步，退到了状态：3 2 __ 。剩余第三个空位没有填数。第三个空位上除了填过的 1，2，没有其他数字可以填。
因此再往后退一步，退到了状态：3 __ __。第二个空位上除了填过的 1，2，没有其他数字可以填。
因此再往后退一步，退到了状态：__ __ __。第一个空位上除了填过的 1，2，3，没有其他数字可以填。
注：以上内容均转载自Acwing——Hasity的题解
代码实现如下：
#include<iostream> using namespace std; const int N=100010; int n; int a[N]; bool st[N]; void dfs(int u) { if(u==n) { for(int i=0;i<n;i++) { cout <<a[i] << ' '; } cout <<endl; } for(int i=1;i<=n;i++) { if(!st[i]) { a[u]=i; st[i]=true; dfs(u+1); st[i]=false; } } } int main() { cin >> n; dfs(0); return 0; }
所以我们可以利用上述问题的思路对这个问题进行求解：
具体实现代码如下：
class Solution {
public:
vector<string> ans;
string strs[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
void dfs(string&digits,int u,string path)
{
if(u==digits.size())
{
ans.push_back(path);
}
else
{
for(auto c:strs[digits[u]-'0'])
dfs(digits,u+1,path+c);
}
}
vector<string> letterCombinations(string digits) {
if(digits.empty())
{
return {};
}
dfs(digits,0,"");
return ans;
}
};（18）四数之和（中等）
实现思路：
思路与三数相加类似
代码实现思路如下：
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
sort(nums.begin(),nums.end());
vector<vector<int>> res;
for(int i=0;i<nums.size();i++)
{
if(i && nums[i]==nums[i-1]) continue;
for(int j=i+1;j<nums.size();j++)
{
if(j>i+1 && nums[j]==nums[j-1]) continue;
for(int k=j+1,u=nums.size()-1;k<u;k++)
{
if(k>j+1 && nums[k]==nums[k-1]) continue;
while(u-1>k && (long)nums[i]+nums[j]+nums[u-1]+nums[k]>=target) u--;
if((long)nums[i]+nums[j]+nums[u]+nums[k]==target)
{
res.push_back({nums[i],nums[j],nums[k],nums[u]});
}
}
}
}
return res;
}
};（19）删除链表倒数第k个节点（中等）
实现思路：
本题实现思路十分简单，我们首先遍历链表得到对应的链表的长度k，因为我们要删除的是倒数第n个节点，所以我们正向删除的就是第k-n个节点，我们找到第k-n-1个节点，将其对应的关系联络起来就可以了。
代码实现如下：（注：对应这种头结点未必存在的问题，我们最好使用哨兵位记录头结点的位置）
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
auto dummy=new ListNode(-1);
dummy->next=head;
int k=0;
for(auto p=dummy;p;p=p->next)
{
k++;
}
auto p=dummy;
for(int i=0;i<k-n-1;i++ ) p=p->next;
p->next=p->next->next;
return dummy->next;
}
};（20）有效的括号（简单）
实现思路：
因为我们要匹配左右括号之间的关系，所以我们可以创建一个栈，如果是左括号就入栈，如果此时右括号与之相匹配的话就删除栈顶与之相对应的左括号（我们观察ASCII表会发现，左右括号ASCII的差最多不超过2，所以我们可以利用此条件判断是否匹配）。
代码实现如下：
class Solution {
public:
bool isValid(string s) {
stack<char> st;
for(auto str:s)
{
if(str=='(' || str=='[' || str=='{') st.push(str);
else if(st.size() && abs(st.top()-str)<=2) st.pop();
else
return false;
}
return st.empty();
}
};希望以上文章对您有帮助！！！
