算法笔记-两数之和、三数之和、四数之和（LeetCode)

青旅半醒 2023-02-14 02:29 40阅读 0赞

### 两数之和 ###

1.两数之和  
题目：给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9
    
    因为 nums[0] + nums[1] = 2 + 7 = 9
    所以返回 [0, 1]

代码：

/**
     * Note: The returned array must be malloced, assume caller calls free().
     */
    int* twoSum(int* nums, int numsSize, int target, int* returnSize){
        
        
        if(nums==NULL) return NULL;
    
      
        int *res = (int*)malloc(sizeof(int)*2);
        *returnSize = 2;
    
        for(int i= 0;i<numsSize;i++) {
        
    
            for(int j = i+1;j<numsSize;j++) {
        
                if(nums[i] + nums[j] == target) {
        
                    res[0] = i;
                    res[1] = j;
                    
                    break;
                }
            }
        }
        return res;
    }

167.两数之和II-输入有序数组  
题目：给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。

函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。

说明:  
返回的下标值（index1 和 index2）不是从零开始的。  
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

示例:

输入: numbers = [2, 7, 11, 15], target = 9
    输出: [1,2]
    解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

int* twoSum(int* numbers, int numbersSize, int target, int* returnSize){
        
        
        
        if(numbers==NULL) return NULL;
    
      
        int *res = (int*)malloc(sizeof(int)*2);
        *returnSize = 2;
    
        for(int i= 0;i<numbersSize-1;i++) {
        
    
            for(int j = i+1;j<numbersSize;j++) {
        
                if(numbers[i] + numbers[j] == target) {
        
                    res[0] = i+1;
                    res[1] = j+1;
                    
                    break;
                }
            }
        }
        return res;
    }

对上述两个题目的总结：  
题目区别：返回的下标是否从0开始  
代码区别：  
1

res[0] = i;
                    res[1] = j;

167

res[0] = i+1;
                    res[1] = j+1;

### 三数之和 ###

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

注意：答案中不可以包含重复的三元组。

示例：

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

代码:

//先将数组进行排序，然后进行三重循环。其中，前两重循环，使用普通遍历即可，需要做一下剪枝。
    //第三重循环，我这里用了二分查找（不用，或许也行），可以优化一下速度
    
    int cmp(const void *a, const void *b) 
    {
        
        return *(int*)a - *(int*)b; // 比较大小
    }
    
    /**
     * 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** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes)
    {
        
        if (nums == NULL || returnSize == NULL || returnColumnSizes == NULL) {
        
            return NULL;
        } 
        // 方便起见，先申请足够的内存
        int max_count = numsSize * numsSize; // 认为足够了
        int **p = (int **)malloc(sizeof(int*) * max_count); 
        if (p == NULL) {
         // 申请内存是否失败
            return NULL;
        }
        *returnColumnSizes = (int*)malloc(sizeof(int) * max_count);
        if (*returnColumnSizes == NULL) {
         // 申请内存是否失败
            free(p); // 释放之前申请的内存
            return NULL;
        }
        memset(*returnColumnSizes, 0, sizeof(int) * max_count);
        *returnSize = 0;
        // 从小到大排序，时间复杂度O(nlogn)
        qsort(nums, numsSize, sizeof(int), cmp);
        /* for (int i = 0; i < numsSize; i++) {
            printf("%d, ", nums[i]);
        }
        printf("\n"); */
        for (int i = 0; i < numsSize; i++) {
        
            if (nums[i] > 0) {
         // 剪枝
                continue;
            }        
            if (i > 0 && nums[i] == nums[i - 1]) {
         // 剪枝
                continue;
            } 
            for (int j = i + 1; j < numsSize; j++) {
        
                if (nums[i] + nums[j] > 0) {
         // 剪枝
                    continue;
                } 
                if (j > i + 1 && nums[j] == nums[j - 1]) {
         // 剪枝
                    continue;
                } 
                // 这里用二分查找，进行优化
                int left = j + 1;
                int right = numsSize - 1;
                while (left <= right) {
        
                    int mid = (left + right) / 2;
                    int sum = nums[i] + nums[j] + nums[mid];
                    // printf("[%d]%d + [%d]%d + [%d]%d = (%d-%d)%d\n", 
                    //      i, nums[i], j, nums[j], mid, nums[mid], left, right, sum);
                    if (sum == 0) {
         // 找到一个解
                        p[*returnSize] = (int*)malloc(sizeof(int) * 3);
                        if (p[*returnSize] == NULL) {
        
                            return NULL;
                        }
                        p[*returnSize][0] = nums[i];
                        p[*returnSize][1] = nums[j];
                        p[*returnSize][2] = nums[mid];
                        (*returnColumnSizes)[*returnSize] = 3;
                        (*returnSize)++;
                        break; // 找到则退出 
                    } else if (sum > 0) {
        
                        right = mid - 1;
                    } else {
        
                        left = mid + 1;
                    }
                }            
            }
        }
        return p;
    }

疑惑：不清楚下面这样子为什么不可以  
此处附上错误代码：

/**
     * 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** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
        
        if(nums==NULL)
            return NULL;
        
        int *res = (int*)malloc(3*sizeof(int));
        *returnSize = 3;
    
        int i,j,k;
    
        for(i=0; i<numsSize-2; i++)
        {
        
            for(j=i+1; j<numsSize-1; j++)
            {
        
                for(k=j+1; k<numsSize; k++)
                {
        
                    if(nums[i]+nums[j]+nums[k]==0)
                    {
        
                        res[0]=i;
                        res[1]=j;
                        res[2]=k;
                        break;
                    }
                }
            }
        }
        return res;
    
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70]  
搜索了一下错误的原因:

*  LeetCode使用了AddressSanitizer检查了是否存在内存非法访问。
 *  在该题目中，是因为数组访问越界，也是绝大部分的内存访问题。

可是我不觉得自己for循环里有问题啊，如果大佬看到了错误或者有思路，愿闻详解，本菜鸟的荣幸

### 四数之和 ###

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]
    ]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200531180106827.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2,size_16,color_FFFFFF,t_70