跳到主要内容

三数之和

· 阅读需 6 分钟
Eureka X
Eureka X
Mr.Nobody

力扣面试经典——15题​

💡 参考代码：​

// 比较函数，用于qsort排序
int compare(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) {
    // 初始化返回结果数量为0
    *returnSize = 0;
    
    // 如果数组长度小于3，无法构成三元组，直接返回
    if (numsSize < 3) {
        return NULL;
    }
    
    // 对数组进行排序，时间复杂度O(nlogn)
    qsort(nums, numsSize, sizeof(int), compare);
    
    // 分配结果数组空间，最坏情况下所有组合都满足条件
    int** result = (int**)malloc(sizeof(int*) * numsSize * numsSize);
    *returnColumnSizes = (int*)malloc(sizeof(int) * numsSize * numsSize);
    
    // 遍历数组，固定第一个数
    for (int i = 0; i < numsSize - 2; i++) {
        // 如果当前数字大于0，由于数组已排序，后面的数字都大于0，三数之和不可能为0
        if (nums[i] > 0) {
            break;
        }
        
        // 跳过重复元素，避免重复的三元组
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }
        
        // 使用双指针法查找另外两个数
        int left = i + 1;        // 左指针指向i之后的第一个元素
        int right = numsSize - 1; // 右指针指向数组末尾
        
        // 双指针向中间移动查找满足条件的组合
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            
            if (sum == 0) {
                // 找到满足条件的三元组
                result[*returnSize] = (int*)malloc(sizeof(int) * 3);
                result[*returnSize][0] = nums[i];
                result[*returnSize][1] = nums[left];
                result[*returnSize][2] = nums[right];
                (*returnColumnSizes)[*returnSize] = 3;
                (*returnSize)++;
                
                // 跳过重复元素
                while (left < right && nums[left] == nums[left + 1]) {
                    left++;
                }
                while (left < right && nums[right] == nums[right - 1]) {
                    right--;
                }
                
                // 移动指针继续查找
                left++;
                right--;
            } else if (sum < 0) {
                // 三数之和小于0，说明需要更大的数，左指针右移
                left++;
            } else {
                // 三数之和大于0，说明需要更小的数，右指针左移
                right--;
            }
        }
    }
    
    return result;
}

📖 总结：​

点击展开题目总结

🤔 三数之和

1️⃣ 题目核心信息​

🎯 功能描述：在给定整数数组中找出所有不重复的三元组，使得三个数的和为0

📥 输入输出：

  • 输入：整数数组nums及其长度numsSize
  • 输出：所有和为0的不重复三元组组成的二维数组，通过returnSize返回结果数量，通过returnColumnSizes返回每行的列数

2️⃣ 实现原理​

💡 核心思路：先对数组排序，然后固定一个数，用双指针在剩余数组中查找另外两个数，使得三数之和为0

📋 实现步骤：

  1. 对输入数组进行排序
  2. 遍历数组，固定第一个数nums[i]
  3. 在nums[i]之后的子数组中使用双指针法查找另外两个数
  4. 左指针指向i+1，右指针指向数组末尾，根据三数之和调整指针位置
  5. 跳过重复元素避免重复三元组

3️⃣ 关键点解析​

🎯 代码技巧​

  • 排序预处理：通过对数组排序，使双指针法成为可能，并便于去重
  • 双指针法：在有序数组中查找两数之和，时间复杂度从O(n²)降到O(n)
  • 去重策略：在遍历和查找过程中跳过重复元素，确保结果不重复

4️⃣ 使用场景​

✅ 适用情况：​

  • 在数组中查找固定元素个数的组合问题
  • 需要找出满足特定和值的数字组合
  • 数据规模适中且对时间复杂度有要求的场景

⚠️ 前提条件：​

  • 输入数组至少包含3个元素
  • 数组元素可以为负数、零或正数

5️⃣ 复杂度分析​

  • ⏱️ 时间复杂度：O(n²)，其中n为数组长度。排序需要O(n log n)，外层循环O(n)，内层双指针O(n)

  • 💾 空间复杂度：O(1)，不考虑返回数组的空间，只使用常数级别的额外空间

6️⃣ 注意事项​

🚩 边界情况：​

  • 数组长度小于3的情况
  • 数组全为正数或全为负数的情况
  • 数组中有大量重复元素的情况

💥 易错点：​

  • 忘记对结果去重，导致重复三元组
  • 双指针移动条件判断错误
  • 边界条件处理不当，可能导致数组越界
  • 忽略排序的重要性，影响算法正确性

7⃣ 补充说明​

以 nums = [-1, 0, 1, 2, -1, -4] 为例：

第一步：排序​

qsort(nums, numsSize, sizeof(int), compare);

排序后：nums = [-4, -1, -1, 0, 1, 2]

第二步：外层循环遍历​

开始遍历数组，固定第一个数：

i = 0，nums[0] = -4​

  • nums[0] = -4 <= 0，继续处理
  • left = 1, right = 5
  • 双指针查找过程：
    • nums[0] + nums[1] + nums[5] = -4 + (-1) + 2 = -3 < 0，left++
    • nums[0] + nums[2] + nums[5] = -4 + (-1) + 2 = -3 < 0，left++
    • nums[0] + nums[3] + nums[5] = -4 + 0 + 2 = -2 < 0，left++
    • nums[0] + nums[4] + nums[5] = -4 + 1 + 2 = -1 < 0，left++
  • left = right，结束本轮

i = 1，nums[1] = -1​

  • nums[1] = -1 <= 0，继续处理
  • left = 2, right = 5
  • 双指针查找过程：
    • nums[1] + nums[2] + nums[5] = -1 + (-1) + 2 = 0 == 0，找到三元组[-1, -1, 2]
      • 记录结果
      • 跳过重复：nums[2] == nums[3]，所以left++，left = 3
      • right--，right = 4
    • nums[1] + nums[3] + nums[4] = -1 + 0 + 1 = 0 == 0，找到三元组[-1, 0, 1]
      • 记录结果
      • left++，left = 4
      • right--，right = 3
  • left > right，结束本轮

i = 2，nums[2] = -1​

  • nums[2] = -1 <= 0，但是nums[2] == nums[1]，跳过避免重复

i = 3，nums[3] = 0​

  • nums[3] = 0 <= 0，继续处理
  • left = 4, right = 5
  • 双指针查找过程：
    • nums[3] + nums[4] + nums[5] = 0 + 1 + 2 = 3 > 0，right--
  • left = right，结束本轮

i = 4，nums[4] = 1​

  • nums[4] = 1 > 0，直接break，后续元素都大于0，不可能找到和为0的三元组

最终结果​

得到两个不重复的三元组：

  1. [-1, -1, 2]
  2. [-1, 0, 1]

这个过程展示了算法如何通过排序和双指针技巧有效地找到所有满足条件的三元组，并通过跳过重复元素来避免重复结果。

这道题我还不理解，明天我一定补上！

加载评论中...