16. 最接近的三数之和

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

例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.
与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

分析：这个与之前做过的三数之和很相似，我们同样需要先将数组排序，然后从i=0开始遍历每个元素，然后从i+1与n-1开始向中间逼近，获得与target值的差绝对值最小的组合。当为0时直接返回结果。

    int threeSumClosest(vector<int>& nums, int target) {
        if (nums.size() < 3) return INT_MIN;  //数组长度小于3时，不存在
        sort(nums.begin(), nums.end());  //  给数组排序
        int sum = nums[0] + nums[1] + nums[2];  //初始化一个和为开始的三个元素
        for (int i = 0; i < nums.size(); i++) {  //  遍历元素
          int j = i+1;  //  左
          int k = nums.size()-1; // 右
        
          while(j < k) {  
              int newSum = nums[i] + nums[j] + nums[k];  // 当前组合的值
            
              if(abs(target - newSum) < abs(target - sum)) {  // 比较当前组合与目标值的差值和保存的小差值之间的大小
                  if (abs(target - newSum) == 0) return newSum;
                  sum = newSum;
              }
            
              if (newSum < target) {  // 当前组合小于目标值的时候， 左边移动，否则右边移动
                  ++j;
              }else {
                  --k;
              }
          }
      }
      return sum;
    }

17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例:
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

说明:

尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

分析：首先我们使用一个函数来获取每一个数字对应的字符，然后我们使用一个递归函数来循环获取每个数字中字符串的可能组合。

vector<string> letterCombinations(string digits) {
    vector<string> res;  //保存结果的集合
    if (digits.size() == 0) return res;  //如果字符串为0，返回空
    combineStr(digits, 0, "", res);  //调用递归函数
    return res;
}

//digits:源字符串； index:源串中的第几个字符； cs：字符串组合；res:结果集合
void combineStr(string digits, int index, string cs, vector<string> &res) {
    if(index == digits.length()) {  //  如果递归到最后一个字符，将组合的字符串保存到结果中
        res.push_back(cs);
    }else {
        string str = charToString(digits[index]);  //获取index字符所代表的字母字符串
        for (int i = 0; i < str.size(); ++i) {  //循环遍历字母字符串
            cs.push_back(str[i]);  //将当前的字母保存到字符串组合中
            combineStr(digits, index+1, cs, res);  //递归遍历下一个字符
            cs.pop_back();  //获得结果后 清空字符串，组合下一个字母
        }
    }
}

string charToString(char c) {
    string res;
    switch(c) {
        case '2':
            res = "abc";
            break;
        case '3':
            res = "def";
            break;
        case '4':
            res = "ghi";
            break;
        case '5':
            res = "jkl";
            break;
        case '6':
            res = "mno";
            break;
        case '7':
            res = "pqrs";
            break;
        case '8':
            res = "tuv";
            break;
        case '9':
            res = "wxyz";
            break;
        default:
            break; 
    }
    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]
]

分析：这和之前我们做的三数之和一样，只是多一个步骤，我们先去一个元素用target减去这个元素，剩下的就是求三数之和的步骤。遍历减去所有的元素得到的就是组合就是四数之和了。

vector<vector<int>> fourSum(vector<int>& nums, int target) {

    vector<vector<int>> res;
    
    if (nums.size() < 4) {  // 数组长度要大于等于4
        return res;
    }

    sort(nums.begin(), nums.end());  // 排序数组
    for (int i = 0; i < nums.size() - 3; ++i) {  //  遍历元素
        if (i > 0 && nums[i] == nums[i-1]) continue;  //  如果i大于0并且元素值与上一个相等，跳过。
        int subTarget = target - nums[i]; //保存`target`减去元素值的结果
        for (int j = i+1; j < nums.size() - 2; ++j) {   //  遍历剩下的元素
            if (nums[j] == nums[j-1] && j != i+1) continue; // 排出相等重复的元素
            int l = j + 1; //左
            int r = (int)nums.size() - 1; //右
            while (l < r) {
                if (nums[j] + nums[l] + nums[r] == subTarget) { // 保存满足要求的组合
                    vector<int> a = {nums[i], nums[j], nums[l], nums[r]};
                    res.push_back(a);
                
                    l++; // 两端向中间逼近
                    r--;
                    while (l < r && nums[l] == nums[l-1]) { // 排除两端的重复元素
                        l++;
                    }
                    while (l < r && nums[r] == nums[r+1]) {
                        r--;
                    }
                }else if (nums[j] + nums[l] + nums[r] < subTarget) { // 结果小于目标，左向右靠近
                    l++;
                }else { // 反之右向左靠近
                    r--;
                }
            }
        }
    }
    return res;
}

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

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

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

说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

分析：我们首先分析一般情况，要找到倒数第n个结点，我们需要知道链表的长度，所以我们需要进行第一次循环，得到链表的长度length。 然后我们再进行第二次循环，得到第n个结点的前一个结点，改变其后继结点即可。

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */

    ListNode* removeNthFromEnd(ListNode* head, int n)  {
        int length = 0;
        auto temp = head;
        while(temp != NULL) {
            temp = temp->next;
            ++length;
        }
        temp = head;
        while(length-n-1) {  //要取n的前一位，所以多-1；
            --n;
            temp = temp->next;
        }
        temp->next = temp->next->next;
        return head;
    }

进阶：在上面我们是用一个指针temp遍历链表获取长度，这里我们可以考虑用两个指针，让其中一个指针先走n步，然后两个指针同时向后移，当第一个指向链表最后一个元素时，后走的指针就恰好走到倒数第n+1个元素。这里我们要考虑一个特殊情况：当n太大而导致第二个指针来不及移动的情况。比如有2个元素，我们要删除倒数第2个，此时第二个指针不会移动。

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode *temp = head;  //第一个指针
    ListNode *tempN = head; // 第二个指针
    while(temp->next != NULL) {
        temp = temp->next;
        n--;
        if(n < 0) tempN = tempN->next;  //第n步后移动第二个指针
    }
    
    if(tempN == head && n > 0) return tempN->next; //第二个指针来不及移动时，直接返回其后继。
    
    tempN->next = tempN->next->next;  //  删除元素
    return head;
}

20. 有效的括号

给定一个只包括'('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1:
输入: "()"
输出: true

示例 2:
输入: "()[]{}"
输出: true

示例 3:
输入: "(]"
输出: false

示例 4:
输入: "([)]"
输出: false

示例 5:
输入: "{[]}"
输出: true

分析：首先，我们判断字符串长度是否为奇数，如果为奇数，则肯定不匹配。然后我们可以用栈来保存字符串，如果字符为左括号，则压入栈；如果字符为右括号，则与栈顶元素比较，如果匹配弹出栈顶元素，同时遍历下一个元素。如果不匹配返回false。

bool isValid(string s) {
    if(s.length()%2 != 0) return false;  // 长度是否为奇数
    stack<char> S;  //栈
    for(int i = 0; i < s.length();i++) {  //遍历元素
        if (s[i] == '(' || s[i] =='[' || s[i] == '{') {  //  为左括号时压入栈
                S.push(s[i]);
        }else {
            if (S.empty()) return false;  //  如果栈空了，返回false
            char target = S.top(); //获取栈顶元素
            if(!isEqual(target,s[i])) return false; 判断是否匹配
            S.pop(); // 弹出栈顶元素
        }
    }
    return S.empty(); //如果最终栈空，则所有元素都匹配完了，否则存在不匹配元素。
}

bool isEqual(char target, char c) { // 元素是否匹配。
    switch (c) {
        case ')':
            if (target == '(') return true;
            return false;
            break;
        case ']':
            if (target == '[') return true;
            return false;
            break;
        case '}':
            if (target == '{') return true;
            return false;
            break;
        default:
            return false;
    }
}