LeetCode第十五题：三数之和

admin
学习
2024-02-26
51热度
0评论

1.题目描述

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

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

示例 1：

输入：nums = [-1,0,1,2,-1,-4]

输出：[[-1,-1,2],[-1,0,1]]

解释： nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。 nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。 nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。注意，输出的顺序和三元组的顺序并不重要。

提示：

3 <= nums.length <= 3000
-10⁵ <= nums[i] <= 10⁵

2.解题思路

解法一：暴力法（不通过）

描述：排序后，三层循环找到所有的可能性。
时间复杂度：O(n^3)。主要的时间开销来自于三层嵌套循环，每层循环遍历整个数组。
空间复杂度：O(1)。
参考代码：

java版：

class Solution{
public List<List<Integer>> threeSum(int[] nums) {
        // 作为结果列表
        List<List<Integer>> res = new ArrayList<>();
        // 数组排序，便于去重
        Arrays.sort(nums);
        // 遍历数组，选第一个数
        for (int i = 0; i < nums.length - 2; i++) {
            // 跳过重复的数字
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            // 遍历数组，选第二个数
            for (int j = i + 1; j < nums.length - 1; j++) {
                // 跳过重复的数字
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                // 遍历数组，选第三个数
                for (int k = j + 1; k < nums.length; k++) {
                    // 跳过重复的数字
                    if (k > j + 1 && nums[k] == nums[k - 1]) {
                        continue;
                    }
                    // 如果三数之和为0，添加到结果列表
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        res.add(Arrays.asList(nums[i], nums[j], nums[k]));
                    }
                }
            }
        }

        return res;
    }
}

C++版：

class Solution {
public:
	vector<vector<int>> threeSum(vector<int>& nums) {
		sort(nums.begin(), nums.end()); // 首先对数组进行排序
		vector<vector<int>> result;

		for (int i = 0; i < nums.size(); ++i) {
			// 避免重复的三元组
			if (i > 0 && 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; k < nums.size(); ++k) {
					// 再次避免重复
					if (k > j + 1 && nums[k] == nums[k - 1]) continue;

					if (nums[i] + nums[j] + nums[k] == 0) {
						result.push_back({ nums[i], nums[j], nums[k] });
					}
				}
			}
		}

		return result;
	}
};

C版：

 // 比较函数，用于qsort
int cmp(const void* a, const void* b) {
	return (*(int*)a - *(int*)b);
}

int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
	// 预先分配足够大的空间，但在实际应用中需要根据具体问题调整大小
	int** result = (int**)malloc(sizeof(int*) * (numsSize * numsSize * numsSize));
	*returnColumnSizes = (int*)malloc(sizeof(int) * (numsSize * numsSize * numsSize));
	*returnSize = 0;

	// 对数组进行排序，便于去重和后续处理
	qsort(nums, numsSize, sizeof(int), cmp);

	for (int i = 0; i < numsSize; ++i) {
		// 跳过重复的数字，避免重复的三元组
		if (i > 0 && nums[i] == nums[i - 1]) continue;

		for (int j = i + 1; j < numsSize; ++j) {
			// 同样跳过重复的数字
			if (j > i + 1 && nums[j] == nums[j - 1]) continue;

			for (int k = j + 1; k < numsSize; ++k) {
				// 再次跳过重复的数字
				if (k > j + 1 && nums[k] == nums[k - 1]) continue;

				if (nums[i] + nums[j] + nums[k] == 0) {
					int* triplet = (int*)malloc(sizeof(int) * 3);
					triplet[0] = nums[i];
					triplet[1] = nums[j];
					triplet[2] = nums[k];
					result[*returnSize] = triplet;
					(*returnColumnSizes)[*returnSize] = 3; // 每个子数组的大小为3
					(*returnSize)++;
				}
			}
		}
	}

	return result;
}

解法二：排序+双指针

描述：排序: 首先对数组进行排序。这一步是必要的，因为排序后可以使用双指针技术，同时也便于跳过重复的元素。遍历: 从左到右遍历排序后的数组。对于每个元素nums[i]，设置两个指针，一个在i之后(left = i + 1)，另一个在数组末尾(right = nums.length - 1)。这样，nums[i]、nums[left]和nums[right]构成了一组候选的三元组。双指针搜索: 对于每个nums[i]，移动left和right指针来寻找和为0的三元组。如果nums[i] + nums[left] + nums[right]的和小于0，说明需要更大的数，因此left指针向右移。如果和大于0，说明需要更小的数，因此right指针向左移。如果和等于0，将这三个数作为一组解加入到结果集中，并移动left和right以跳过重复的元素。避免重复: 在遍历和双指针搜索过程中，如果遇到连续相同的数字，则跳过，以避免将重复的三元组加入到结果集中。
时间复杂度：O(n^2)。n是nums数组的长度。
空间复杂度：O(logn)。n是数组 nums的长度。
参考代码：

java版：

class Solution{
public List<List<Integer>> threeSum(int[] nums) {
        // 先排序
        Arrays.sort(nums);

        List<List<Integer>> res = new ArrayList<>();

        // 遍历数组
        for (int i = 0; i < nums.length - 2; i++) {
            // 如果选的第一个数字已经用过了，跳过
            if (i > 0 && nums[i] == nums[i - 1])
                continue;
            int left = i + 1;
            int right = nums.length - 1;
            // 遍历数组，固定第一个数，然后用双指针查找其他两个数
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                // 如果符合
                if (sum == 0) {
                    res.add(Arrays.asList(nums[i], nums[left], nums[right]));

                    // 跳过所有重复的左指针值
                    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 res;
    }
}

C++版：

class Solution {
public:
	vector<vector<int>> threeSum(vector<int>& nums) {
		// 先对数组进行排序
		sort(nums.begin(), nums.end());

		vector<vector<int>> result;
		// 遍历数组，固定第一个数，然后用双指针查找其他两个数
		for (int i = 0; i < nums.size() - 2; i++) {
			// 跳过重复的数，避免结果重复
			if (i > 0 && nums[i] == nums[i - 1]) continue;

			int left = i + 1;
			int right = nums.size() - 1;
			while (left < right) {
				int sum = nums[i] + nums[left] + nums[right];

				if (sum == 0) {
					// 找到一组解，并将其加入结果集
					result.push_back({ nums[i], nums[left], nums[right] });
					// 跳过所有重复的左指针值
					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;
	}
};

C版：

// 比较函数，用于qsort
int compare(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

// 三数之和的函数实现
// nums: 输入的数组
// numsSize: 数组的大小
// returnSize: 返回的结果数组的大小
// 注意：返回的数组需要在外部释放内存
int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    // 先对数组进行排序
    qsort(nums, numsSize, sizeof(int), compare);

    // 动态分配结果数组的最大可能空间
    int **res = (int **)malloc(numsSize * numsSize * sizeof(int *));
    *returnColumnSizes = (int *)malloc(numsSize * numsSize * sizeof(int));
    *returnSize = 0;
    
    // 遍历数组，固定一个数，然后用双指针寻找其他两个数
    for (int i = 0; i < numsSize; ++i) {
        // 跳过重复的数
        if (i > 0 && nums[i] == nums[i - 1]) continue;

        int left = i + 1, right = numsSize - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum == 0) {
                // 找到一组解，分配空间并保存这个解
                res[*returnSize] = (int *)malloc(3 * sizeof(int));
                res[*returnSize][0] = nums[i];
                res[*returnSize][1] = nums[left];
                res[*returnSize][2] = nums[right];
                (*returnColumnSizes)[*returnSize] = 3; // 每个解都是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 res;
}

解法三：哈希表法

描述：首先，遍历整个数组，使用一个哈希表来存储每个数字及其出现的次数。这样做是为了后续快速判断一个数字是否存在于数组中。然后，使用两层嵌套循环遍历数组中的每对数字，对于每对数字nums[i]和nums[j]，计算它们的和的相反数-nums[i]-nums[j]，并在哈希表中查找这个相反数是否存在。如果存在，那么这三个数字就构成了一个可能的解。为了避免重复的解，可以在找到一个解之前检查它是否已经被添加过。最后，从存储唯一解的哈希表中收集所有解，并转换成所需的输出格式。
时间复杂度：O(n^2)。两层循环嵌套复杂度为O(n^2)。
空间复杂度：O(n)。这个哈希表用于存储数组中每个数字及其出现的次数。在最坏的情况下，如果数组中的每个数字都不相同，那么这个哈希表的大小将与输入数组的大小相同，即O(n)，其中n是数组的长度。
参考代码：

java版：

class Solution{
public List<List<Integer>> threeSum(int[] nums) {
        // 使用Set来自动去重
        Set<List<Integer>> res = new HashSet<>();
        // 如果数组长度小于3，直接返回空列表
        if (nums.length < 3)
            return new ArrayList<>(res);
        // 对数组进行排序，帮助去重
        Arrays.sort(nums);

        for (int i = 0; i < nums.length - 2; i++) {
            // 使用哈希表存储已遍历的元素
            Set<Integer> seen = new HashSet<>();
            // 固定了nums[i]后找另外两个
            for (int j = i + 1; j < nums.length; j++) {
                // 确定了两个数，看第三个数应该是什么
                int complement = -nums[i] - nums[j];
                // 如果哈希表里面有第三个数，说明找到了一组解
                if (seen.contains(complement)) {
                    List<Integer> triplet = Arrays.asList(nums[i], nums[j], complement);
                    // 把找到的解排序，方便去重，例如找到[2, -1, -1]，后面又找到[-1, -1, 2]
                    // 实际上是相同的解，但顺序不同，也会被误认为两个解，固定排序，利用Set的自动去重可以解决这个问题
                    Collections.sort(triplet);
                    // 把找到的解添加到结果集
                    res.add(triplet);
                }
                // 哈希表里面没有第三个数，就把第二个数存入哈希表，方便后面找
                // 例如[-1, 0, 1, 2, -1, -4]排序后[-4, -1, -1, 0, 1, 2]
                // 固定nums[i]=-1,当遍历到0时，我们尝试去找1，因为complement=1
                // 此时seen没有1，所以不做其他操作，就把0加到seen中，等遍历到1时
                // seen中可以找到0，说明存在一个解
                seen.add(nums[j]);
            }
        }
        // 将Set转换为List返回
        return new ArrayList<>(res);
    }
}

C++版：

class Solution {
public:
	vector<vector<int>> threeSum(vector<int>& nums) {
		// 先对数组进行排序
		sort(nums.begin(), nums.end());

		vector<vector<int>> result;
		// 遍历数组，固定第一个数，然后用双指针查找其他两个数
		for (int i = 0; i < nums.size() - 2; i++) {
			// 跳过重复的数，避免结果重复
			if (i > 0 && nums[i] == nums[i - 1]) continue;

			int left = i + 1;
			int right = nums.size() - 1;
			while (left < right) {
				int sum = nums[i] + nums[left] + nums[right];

				if (sum == 0) {
					// 找到一组解，并将其加入结果集
					result.push_back({ nums[i], nums[left], nums[right] });
					// 跳过所有重复的左指针值
					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;
	}
};

C版(不通过)：

class Solution {
public:
	vector<vector<int>> threeSum(vector<int>& nums) {
		// 结果去重，使用set自动排序并去重
		set<vector<int>> result;
		// 哈希表用于快速查找
		unordered_set<int> seen;
		// 先排序，便于去重
		sort(nums.begin(), nums.end());

		for (int i = 0; i < nums.size() - 2; i++) {
			// 避免固定同一个数，导致重复解
			if (i > 0 && nums[i] == nums[i - 1]) continue;

			seen.clear();
			for (int j = i + 1; j < nums.size(); j++) {
				int complement = -nums[i] - nums[j];
				// 如果complement在seen中，说明找到了一组解
				if (seen.find(complement) != seen.end()) {
					vector<int> triplet = { nums[i],nums[j],complement };
					// 把找到的解排序，方便去重，例如找到[2, -1, -1]，后面又找到[-1, -1, 2]
					// 实际上是相同的解，但顺序不同，也会被误认为两个解，固定排序，利用Set的自动去重可以解决这个问题
					sort(triplet.begin(), triplet.end());
					// 把找到的解添加到结果集
					result.insert(triplet);
				}
				// 哈希表里面没有第三个数，就把第二个数存入哈希表，方便后面找
				// 例如[-1, 0, 1, 2, -1, -4]排序后[-4, -1, -1, 0, 1, 2]
				// 固定nums[i]=-1,当遍历到0时，我们尝试去找1，因为complement=1
				// 此时seen没有1，所以不做其他操作，就把0加到seen中，等遍历到1时
				// seen中可以找到0，说明存在一个解
				seen.insert(nums[j]);
			}
		}
		// 将set转换为vector<vector<int>>返回
		vector<vector<int>> results(result.begin(), result.end());

		return results;
	}
};

解法四：二分查找法

描述：首先对输入数组进行排序，这是使用二分查找的前提条件。遍历排序后的数组，固定前两个数（nums[i]和nums[j]），这两个数分别通过外层和内层循环来确定。为避免添加重复的三元组到结果中，如果当前数字与前一个数字相同，就跳过这个数字。对于每一对固定的数，计算第三个数的目标值（target = -(nums[i] + nums[j])），然后在当前固定数之后的数组部分使用二分查找来查找这个目标值。如果找到了目标值，将三个数作为一个解添加到结果列表中。已经通过跳过相同的nums[i]或nums[j]来部分去重。二分查找确保了每次查找的范围是唯一的，从而避免了重复查找同一个target。
时间复杂度：O(n^2)。两层循环，为O(n^2)。二分查找，O(logn)。但是二分查找的操作是在已经通过两层循环固定了两个数之后进行的。这意味着，对于每一对数的组合，我们只需要额外的O(logn)时间就能完成第三个数的查找。因此，尽管每一对数都需要进行二分查找，这个查找步骤的成本已经包含在了每次内层循环的迭代中。O(n^2)+O(logn)。也就是O(n^2)。
空间复杂度：O(logn)。主要由排序算法的递归调用栈占用。
参考代码：

java版：

class Solution{
public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);

        List<List<Integer>> res = new ArrayList<>();
        // 第一层循环，遍历数组，固定第一个数
        for (int i = 0; i < nums.length - 2; i++) {
            // 跳过数组中相同的元素，避免重复的三元组
            if (i > 0 && nums[i] == nums[i - 1])
                continue;
            // 第二层循环，固定第二个数
            for (int j = i + 1; j < nums.length - 1; j++) {
                // 同样跳过重复元素
                if (j > i + 1 && nums[j] == nums[j - 1])
                    continue;
                // 计算第三个数的目标值（使三数之和为0）
                int targrt = -nums[i] - nums[j];
                // 使用二分查找法在剩下的数组中查找第三个数
                if (binarySearch(nums, j + 1, nums.length - 1, targrt)) {
                    // 如果找到了，将这三个数作为一组结果添加到结果列表中
                    res.add(Arrays.asList(nums[i], nums[j], targrt));
                }
            }
        }
        return res;
    }

    // 二分查找函数
    private boolean binarySearch(int[] nums, int left, int right, int targrt) {
        while (left <= right) {
            // 计算中间位置
            int mid = left + (right - left) / 2;
            // 如果找到目标值，返回true
            if (nums[mid] == targrt)
                return true;
            // 如果中间的数小于目标值，搜索右半边
            else if (nums[mid] < targrt)
                left = mid + 1;
            // 如果中间的数大于目标值，搜索左半边
            else
                right = mid - 1;
        }
        // 如果没有找到，返回false
        return false;
    }
}

C++版：

class Solution {
public:
	vector<vector<int>> threeSum(vector<int>& nums) {
		sort(nums.begin(), nums.end());

		vector<vector<int>> result;
		// 遍历数组，固定第一个数
		for (int i = 0; i < nums.size(); i++) {
			// 跳过重复的数，以避免重复的三元组
			if (i > 0 && 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;
				// 计算第三个数的目标值
				int target = -nums[i] - nums[j];
				// 使用二分查找寻找第三个数
				// 注意：二分查找的范围是[j+1, nums.size())
				auto it = lower_bound(nums.begin() + j + 1, nums.end(), target);
				// 检查是否找到目标值，并且不超出数组范围
				if (it != nums.end() && *it == target) {
					// 如果找到了，添加到结果集
					result.push_back({ nums[i],nums[j],*it });
				}
			}
		}
		return result;
	}
};

C版：

// 用于qsort的比较函数
int compare(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

// 自定义的二分查找函数
int binarySearch(int* nums, int start, int end, int target) {
    while (start <= end) {
        int mid = start + (end - start) / 2;
        if (nums[mid] == target) return mid; // 找到目标
        else if (nums[mid] < target) start = mid + 1; // 在右侧查找
        else end = mid - 1; // 在左侧查找
    }
    return -1; // 未找到
}

int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    qsort(nums, numsSize, sizeof(int), compare); // 对数组进行排序

    // 初始化结果数组和列大小数组
    int** result = malloc(sizeof(int*) * (numsSize * numsSize));
    *returnColumnSizes = malloc(sizeof(int) * (numsSize * numsSize));
    *returnSize = 0;

    for (int i = 0; i < numsSize - 2; i++) {
        if (i > 0 && nums[i] == nums[i-1]) continue; // 跳过重复元素

        for (int j = i + 1; j < numsSize - 1; j++) {
            if (j > i + 1 && nums[j] == nums[j-1]) continue; // 跳过重复元素

            int target = -(nums[i] + nums[j]);
            int index = binarySearch(nums, j + 1, numsSize - 1, target); // 在剩余数组中二分查找

            if (index != -1) { // 如果找到了符合条件的三元组
                result[*returnSize] = malloc(sizeof(int) * 3); // 为新的三元组分配空间
                result[*returnSize][0] = nums[i];
                result[*returnSize][1] = nums[j];
                result[*returnSize][2] = target;
                (*returnColumnSizes)[*returnSize] = 3; // 设置列大小
                (*returnSize)++; // 结果数量增加
            }
        }
    }

    return result;
}