第15题：三数之和
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum

思路
使用3个指针，分别代表三元组中最左、中间和最右的数，然后通过中间的指针和最右指针的移动来遍历数组。

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
 int cmp(const void *a,const void *b)
{
    return *(int*)a - *(int*)b;
}
int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
       *returnSize = 0;
   if(numsSize < 3)  return NULL;
   

    qsort(nums,numsSize,sizeof(int),cmp);
    
   int **ans = (int **)malloc(sizeof(int *) * numsSize *numsSize);
   *returnColumnSizes = (int *)malloc(sizeof(int) * numsSize* numsSize) ;
   int left, mid, right, sum;
    
   
   for(left = 0;left < numsSize - 2;left++)
   {
       if(nums[left] > 0) return ans;
       if(left > 0 && nums[left] == nums[left-1])  continue;
       mid = left + 1;
       right = numsSize - 1;
       while(mid < right)
       {
           sum = nums[left] + nums[mid] + nums[right];
           if(sum == 0)
           {
               ans[*returnSize] = (int *)malloc(sizeof(int)*3);
             
                (*returnColumnSizes)[*returnSize] = 3;
                ans[*returnSize][0] = nums[left];
                ans[*returnSize][1] = nums[mid];
                ans[*returnSize][2] = nums[right];
                *returnSize+=1;     //注意，*的优先级与+ 相同，结合方向从有到左，,*returnSize++  等同于 *(returnSize++)
                while(mid < right && nums[mid] == nums[++mid]);   
                while(mid < right  && nums[right] == nums[--right]) ; 
           }
           else if(sum < 0)
           {
               mid ++;

           }
           else   right--;
           
       }
       
   }
    return ans;
}

第16题：最接近的三数之和
给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。

返回这三个数的和。

假定每组输入只存在恰好一个解。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum-closest

int compare(const void *a, const void*b)
{
    return *(int *)a - *(int *)b;
}
int threeSumClosest(int* nums, int numsSize, int target){
    qsort(nums, numsSize, sizeof(int), compare);
    int left, mid, right, sum1, sum2;
    
    
    sum1 =  nums[0] + nums[1] + nums[2];
    
    for(left = 0; left < numsSize-2; left ++)
    {
        mid = left + 1;
        right = numsSize - 1;
        
        while(mid < right)
        {
            sum2 = nums[left] + nums[mid] + nums[right];
            if(abs(sum1 - target) > abs(sum2 - target))
            {
                sum1 = sum2;
                
            }
            if(sum2 >= target)  while(mid < right && nums[right] == nums[--right]);
            else    while(mid < right && nums[mid] == nums[++mid]); 
        }
    }
    return sum1;
}

第17题：电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number

思路
寻找字典序排列时每个字母位置字母出现的规律。具体见代码。

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

char ** letterCombinations(char * digits, int* returnSize){
    *returnSize = 0;
    int len = strlen(digits);
    if(len == 0)
    {
        
        return NULL;
    }
    
    
    char  f[8][5] = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    int i, j, k, t;
    int num[8], l[8];
    for( i = 0; i < len; i++)    //每个位置的数字对应的字母的个数
    {
        num[i] = strlen(f[digits[i]-'0'-2]);
    }
    for( i = 0; i < len; i++)    //第i个位置之前的排列数，即位置i上每个字母出现几个区间
    {
        if(i == 0) l[0] = 1;
        else l[i] =num[i-1] * l[i-1];
    }
    *returnSize = l[len-1] * num[len-1];
    int m[8];
    for(i = len-1; i >= 0; i--)    //第i个位置之后的排列数，即位置i上每个字母在一个区间出现几次
    {
        if(i == len-1) m[i] = 1;
        else m[i] = num[i+1] * m[i+1];
    }
    int tmp;
    char **ans = (char **) malloc ( sizeof(char *) * (*returnSize));
    for(i = 0; i < *returnSize; i++)
    {
        ans[i] = (char *) malloc(sizeof(char) * (len + 1));
        
    }
    /*数字所在位置为i,字母为数字对应的第j个字母，那么该字母出现在l[i]个区间内，
    每个区间长度为m[i],第k个区间位置为:k* m[i] *num[i]+ j *m[i]  ~ (k*m[i]*num[i] +j*m[i] + m[i]-1)*/
    for(i = 0; i < len; i++)   //i表示字母的位置
    {
        
        for(j = 0; j < num[i]; j++)   //j表示该字符是数字对应的字母的次序
        {
            
           for(k = 0; k < l[i]; k++)
           {
               tmp = k * m[i] *num[i] + j *m[i];
               for(t = 0; t < m[i]; t++)
               {
                   ans[tmp + t][i] = f[digits[i] - '0' -2][j];
                  
               }
           }

        }
    }
    for(i = 0; i < *returnSize; i++)
    {
        
        ans[i][len] = '\0';
    }
    return ans;
}

第18题：四数之和给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/4sum

思路
与“三数之和”类似。

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
 int cmp(const void *a, const void *b)
 {
     return *(int *)a - *(int *)b;
 }
int** fourSum(int* nums, int numsSize, int target, int* returnSize, int** returnColumnSizes){
    *returnSize = 0;
    if(numsSize < 4 )  return NULL;
    
    qsort(nums, numsSize, sizeof(int), cmp);

    if((long)nums[numsSize-1] +nums[numsSize-2] + nums[numsSize-3] + nums[numsSize-4] < target)  return NULL;
    int i, j ,k ,t;
    
    long sum ,tmp;
    *returnColumnSizes = (int **)malloc(sizeof(int *) * numsSize*numsSize);
    int **ans = (int **)malloc(sizeof(int *) * numsSize*numsSize);
    for(i = 0; i < numsSize - 3; i++)
    {
        if(i > 0 && nums[i] == nums[i-1])  continue; 
        if((long)nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target) return ans;
        for(j = i + 1; j < numsSize -2; j ++)
        {
            if(j > i+1 && nums[j] == nums[j-1]) continue;
            if((long)nums[i] + nums[j] + nums[numsSize-1] + nums[numsSize-2] < target) continue;
            k = j + 1;
            t = numsSize - 1;
            tmp = nums[i] + nums[j];
            while(k < t)
            {
                
                sum = tmp + nums[k] +nums[t];
                if(sum == target) 
                {
                    ans[*returnSize] = (int *)malloc(sizeof(int) * 4);
                    (*returnColumnSizes)[*returnSize] = 4;
                    ans[*returnSize][0] = nums[i];
                    ans[*returnSize][1] = nums[j];
                    ans[*returnSize][2] = nums[k];
                    ans[*returnSize][3] = nums[t];
                    
                    *returnSize += 1;
                    while(k < t && nums[k] == nums[k+1]) k++;
                    while(k < t && nums[t] == nums[t-1]) t--;
                    k++;
                    t--;
                }
                else if(sum < target)  k++;
                else t--;

                
            }
        }
        
    }
    return ans;
}

第19题：删除链表的导数第N个结点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

来源：LeetCode
链接：19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode） (leetcode-cn.com)

思路
先遍历链表，得到链表的长度，然后从头得到要删除结点的前一个结点，然后进行删除操作。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
    struct ListNode *s, *t;
    t = s = head;
    int len = 0;;
    while(s)
    {
        s = s->next;
        len++;
    }
    int i;
    s = t;
    if(n == len) 
    {
        s = s->next;
        return s;
    }
    for(i = 0; i < len - n -1; i++)
    {
        s = s->next;
    }
    
    s->next = s->next->next;
    return t;
}