【力扣Leetcode题解系列之0015—Sum 三数之和】
15. 3 Sum 三数之和：多语言实现、分析与拓展
一、题目分析
给定一个包含 n 个整数的数组 nums，找出数组中所有满足 a + b + c = 0 的唯一三元组 (a, b, c)。注意返回的解集不能包含重复的三元组。
二、常用解法
排序 + 双指针法
- 思路：
- 首先对数组
nums进行排序。排序后，数组元素按升序排列，方便后续利用双指针法进行查找。 - 遍历排序后的数组，对于每个元素
nums[i]，我们使用双指针法在剩余的数组元素中寻找两个数，使得它们与nums[i]的和为 0。具体做法是，初始化两个指针，一个指向i + 1（左指针left），另一个指向数组末尾（右指针right）。 - 计算
nums[i] + nums[left] + nums[right]的和sum。如果sum等于 0，则找到了一个满足条件的三元组，将其加入结果集，并移动左指针和右指针以避免重复结果（通过跳过相同元素）。如果sum小于 0，说明当前和偏小，需要增大和，因此将左指针右移；如果sum大于 0，说明当前和偏大，需要减小和，因此将右指针左移。 - 继续遍历数组，重复上述过程，直到遍历完整个数组。
- 首先对数组
- 优点：这种方法通过排序和双指针的结合，避免了暴力解法中大量的重复计算，大大提高了效率。排序的时间复杂度为 (O(n \\log n))，后续的双指针遍历时间复杂度为 (O(n^2))，总体时间复杂度为 (O(n^2))，相较于暴力解法的 (O(n^3)) 有显著提升。
统计频率 + 双指针法（题目中给出的方法）
- 思路：
- 首先使用哈希表（如Python中的
collections.Counter）统计数组中每个元素出现的频率，并获取去重后的元素列表并排序。 - 通过两重循环遍历去重后的元素列表，对于每对元素
values[l]和values[r]，计算需要的第三个元素t = 0 - values[l] - values[r]。 - 判断
t是否在原数组中出现过，并且根据t与values[l]、values[r]的关系以及其在原数组中的频率，确定是否构成满足条件的三元组。例如，当t等于 0 且其频率至少为 3 时，或者t等于values[l]或values[r]且其频率至少为 2 时，或者l等于r且values[l]的频率至少为 2 且t不等于values[l]时，或者t既不等于values[l]也不等于values[r]且l不等于r时，都可能构成满足条件的三元组。 - 为了避免返回重复的三元组，使用集合（如Python中的
set）记录已经处理过的三元组。
- 首先使用哈希表（如Python中的
- 优点：这种方法在一定程度上也能有效地找到满足条件的三元组，并且通过统计频率可以更细致地处理元素重复的情况。其时间复杂度为 (O(n^2))，空间复杂度为 (O(n))，与排序 + 双指针法在时间和空间复杂度上相当，但实现细节相对复杂。
三、多语言实现
Python实现
import collectionsclass Solution: def threeSum(self, nums): count = collections.Counter(nums) values = list(count.keys()) values.sort() N = len(values) res = [] visited = set() for l in range(N): for r in range(l, N): t = 0 - values[l] - values[r] if t in count: if (t == 0 and count[t] >= 3) \\ or (((t == values[l] and t!= values[r]) or (t == values[r] and t!= values[l])) and count[t] >= 2) \\ or (l == r and values[l]!= t and count[values[l]] >= 2) \\ or (t!= values[l] and t!= values[r] and l!= r): curlist = sorted([values[l], t, values[r]]) finger = \"#\".join(map(str, curlist)) if finger not in visited: res.append(curlist) visited.add(finger) return res def threeSumSortAndTwoPointer(self, nums): nums.sort() n = len(nums) result = [] for i in range(n - 2): if i > 0 and nums[i] == nums[i - 1]: continue left, right = i + 1, n - 1 while left < right: sum_val = nums[i] + nums[left] + nums[right] if sum_val == 0: result.append([nums[i], nums[left], nums[right]]) while left < right and nums[left] == nums[left + 1]: left += 1 while left < right and nums[right] == nums[right - 1]: right -= 1 left += 1 right -= 1 elif sum_val < 0: left += 1 else: right -= 1 return resultJava实现
import java.util.*;public class ThreeSum { public List<List<Integer>> threeSum(int[] nums) { Map<Integer, Integer> count = new HashMap<>(); for (int num : nums) { count.put(num, count.getOrDefault(num, 0) + 1); } List<Integer> values = new ArrayList<>(count.keySet()); Collections.sort(values); int N = values.size(); List<List<Integer>> res = new ArrayList<>(); Set<String> visited = new HashSet<>(); for (int l = 0; l < N; l++) { for (int r = l; r < N; r++) { int t = 0 - values.get(l) - values.get(r); if (count.containsKey(t)) { if ((t == 0 && count.get(t) >= 3) || (((t == values.get(l) && t!= values.get(r)) || (t == values.get(r) && t!= values.get(l))) && count.get(t) >= 2) || (l == r && values.get(l)!= t && count.get(values.get(l)) >= 2) || (t!= values.get(l) && t!= values.get(r) && l!= r)) { List<Integer> curList = new ArrayList<>(); curList.add(values.get(l)); curList.add(t); curList.add(values.get(r)); Collections.sort(curList); String finger = String.join(\"#\", curList.stream().map(String::valueOf).toArray(String[]::new)); if (!visited.contains(finger)) { res.add(curList); visited.add(finger); } } } } } return res; } public List<List<Integer>> threeSumSortAndTwoPointer(int[] nums) { Arrays.sort(nums); int n = nums.length; List<List<Integer>> result = new ArrayList<>(); for (int i = 0; i < n - 2; i++) { if (i > 0 && nums[i] == nums[i - 1]) { continue; } int left = i + 1; int right = n - 1; while (left < right) { int sum = nums[i] + nums[left] + nums[right]; if (sum == 0) { List<Integer> triple = new ArrayList<>(); triple.add(nums[i]); triple.add(nums[left]); triple.add(nums[right]); result.add(triple); while (left < right && nums[left] == nums[left + 1]) { left++; } while (left < right && nums[right] == nums[right - 1]) { right--; } left++; right--; } else if (sum < 0) { left++; } else { right--; } } } return result; }}C实现
#include #include #include // 比较函数，用于qsort排序int compare(const void *a, const void *b) { return (*(int *) a - *(int *) b);}// 辅助函数，用于判断三元组是否已存在int exists(int **result, int size, int *triplet) { for (int i = 0; i < size; i++) { if (result[i][0] == triplet[0] && result[i][1] == triplet[1] && result[i][2] == triplet[2]) { return 1; } } return 0;}// 统计频率 + 双指针法int **threeSum(int *nums, int numsSize, int *returnSize, int **returnColumnSizes) { // 统计频率 int maxVal = 0, minVal = 0; for (int i = 0; i < numsSize; i++) { if (nums[i] > maxVal) { maxVal = nums[i]; } if (nums[i] < minVal) { minVal = nums[i]; } } int range = maxVal - minVal + 1; int *count = (int *) calloc(range, sizeof(int)); for (int i = 0; i < numsSize; i++) { count[nums[i] - minVal]++; } int *values = (int *) malloc(numsSize * sizeof(int)); int valuesSize = 0; for (int i = 0; i < range; i++) { if (count[i] > 0) { values[valuesSize++] = i + minVal; } } qsort(values, valuesSize, sizeof(int), compare); int **result = (int **) malloc(numsSize * numsSize * sizeof(int *)); *returnColumnSizes = (int *) malloc(numsSize * numsSize * sizeof(int)); *returnSize = 0; for (int l = 0; l < valuesSize; l++) { for (int r = l; r < valuesSize; r++) { int t = 0 - values[l] - values[r]; int tIndex = t - minVal; if (tIndex >= 0 && tIndex < range && count[tIndex] > 0) { if ((t == 0 && count[tIndex] >= 3) || (((t == values[l] && t!= values[r]) || (t == values[r] && t!= values[l])) && count[tIndex] >= 2) || (l == r && values[l]!= t && count[values[l] - minVal] >= 2) || (t!= values[l] && t!= values[r] && l!= r)) { int triplet[3] = {values[l], t, values[r]}; qsort(triplet, 3, sizeof(int), compare); if (!exists(result, *returnSize, triplet)) { result[*returnSize] = (int *) malloc(3 * sizeof(int)); (*returnColumnSizes)[*returnSize] = 3; result[*returnSize][0] = triplet[0]; result[*returnSize][1] = triplet[1]; result[*returnSize][2] = triplet[2]; (*returnSize)++; } } } } } free(count); free(values); return result;}// 排序 + 双指针法int **threeSumSortAndTwoPointer(int *nums, int numsSize, int *returnSize, int **returnColumnSizes) { qsort(nums, numsSize, sizeof(int), compare); int **result = (int **) malloc(numsSize * numsSize * sizeof(int *)); *returnColumnSizes = (int *) malloc(numsSize * numsSize * sizeof(int)); *returnSize = 0; for (int i = 0; i < numsSize - 2; i++) { if (i > 0 && nums[i] == nums[i - 1]) { continue; } int left = i + 1; int right = numsSize - 1; while (left < right) { int sum = nums[i] + nums[left] + nums[right]; if (sum == 0) { result[*returnSize] = (int *) malloc(3 * sizeof(int)); (*returnColumnSizes)[*returnSize] = 3; result[*returnSize][0] = nums[i]; result[*returnSize][1] = nums[left]; result[*returnSize][2] = nums[right]; (*```c (*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) { left++; } else { right--; } } } return result;}C++实现
#include #include #include #include using namespace std;class Solution {public: vector<vector<int>> threeSum(vector<int>& nums) { unordered_map<int, int> count; for (int num : nums) { count[num]++; } vector<int> values; for (auto it : count) { values.push_back(it.first); } sort(values.begin(), values.end()); int N = values.size(); vector<vector<int>> res; unordered_set<string> visited; for (int l = 0; l < N; l++) { for (int r = l; r < N; r++) { int t = 0 - values[l] - values[r]; if (count.find(t) != count.end()) { if ((t == 0 && count[t] >= 3) || (((t == values[l] && t != values[r]) || (t == values[r] && t != values[l])) && count[t] >= 2) || (l == r && values[l] != t && count[values[l]] >= 2) || (t != values[l] && t != values[r] && l != r)) { vector<int> curList = {values[l], t, values[r]}; sort(curList.begin(), curList.end()); string finger = to_string(curList[0]) + \"#\" + to_string(curList[1]) + \"#\" + to_string(curList[2]); if (visited.find(finger) == visited.end()) { res.push_back(curList); visited.insert(finger); } } } } } return res; } vector<vector<int>> threeSumSortAndTwoPointer(vector<int>& nums) { sort(nums.begin(), nums.end()); int n = nums.size(); vector<vector<int>> result; for (int i = 0; i < n - 2; i++) { if (i > 0 && nums[i] == nums[i - 1]) { continue; } int left = i + 1; int right = n - 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) { left++; } else { right--; } } } return result; }};Go实现
package mainimport ( \"fmt\" \"sort\" \"strconv\" \"strings\")func threeSum(nums []int) [][]int { count := make(map[int]int) for _, num := range nums { count[num]++ } var values []int for num := range count { values = append(values, num) } sort.Ints(values) var res [][]int visited := make(map[string]bool) for l := 0; l < len(values); l++ { for r := l; r < len(values); r++ { t := 0 - values[l] - values[r] if count[t] > 0 { if (t == 0 && count[t] >= 3) || (((t == values[l] && t != values[r]) || (t == values[r] && t != values[l])) && count[t] >= 2) || (l == r && values[l]!= t && count[values[l]] >= 2) || (t!= values[l] && t!= values[r] && l!= r) { curList := []int{values[l], t, values[r]} sort.Ints(curList) finger := strings.Join(strings.Fields(fmt.Sprint(curList)), \"#\") if!visited[finger] { res = append(res, curList) visited[finger] = true } } } } } return res}func threeSumSortAndTwoPointer(nums []int) [][]int { sort.Ints(nums) n := len(nums) var result [][]int for i := 0; i < n-2; i++ { if i > 0 && nums[i] == nums[i-1] { continue } left, right := i+1, n-1 for left < right { sum := nums[i] + nums[left] + nums[right] if sum == 0 { result = append(result, []int{nums[i], nums[left], nums[right]}) for left < right && nums[left] == nums[left+1] { left++ } for left < right && nums[right] == nums[right-1] { right-- } left++ right-- } else if sum < 0 { left++ } else { right-- } } } return result}算法复杂性分析
排序 + 双指针法
- 时间复杂度：排序操作的时间复杂度为 (O(n \\log n))，其中 (n) 是数组的长度。之后的双指针遍历，对于每个元素（最多 (n) 个），双指针移动的次数最多为 (n) 次，所以这部分的时间复杂度为 (O(n^2))。总体时间复杂度为 (O(n^2))，因为 (O(n^2)) 的增长速度快于 (O(n \\log n))。
- 空间复杂度：除了输入数组外，使用的额外空间主要是结果集，在最坏情况下，结果集可能包含 (O(n^2)) 个三元组，但这部分空间通常被视为输出空间。如果不考虑输出空间，算法使用的额外空间为常数级（如指针变量等），所以空间复杂度为 (O(1))。
统计频率 + 双指针法
- 时间复杂度：统计频率的过程需要遍历数组一次，时间复杂度为 (O(n))。之后的两重循环遍历去重后的元素列表，假设去重后元素个数为 (m)（(m \\leq n)），时间复杂度为 (O(m^2))，总体时间复杂度仍为 (O(n^2))，因为 (m) 与 (n) 同阶。
- 空间复杂度：使用哈希表统计频率需要 (O(n)) 的空间，去重后的元素列表最多占用 (O(n)) 的空间，集合用于记录已访问的三元组，在最坏情况下也可能占用 (O(n^2)) 的空间，但如果假设结果集大小远小于 (n^2)，则主要空间复杂度为 (O(n))。
实现的关键点和难度
关键点
- 去重处理：无论是哪种方法，都需要妥善处理结果集中的重复三元组问题。排序 + 双指针法通过在遍历和移动指针过程中跳过相同元素来避免重复；统计频率 + 双指针法则通过使用集合记录已处理的三元组来防止重复。
- 指针移动逻辑：在排序 + 双指针法中，根据当前三个数的和与目标值（0）的比较结果，正确移动左右指针以调整和的大小，是找到满足条件三元组的关键。
- 频率统计与条件判断：统计频率 + 双指针法中，准确统计每个元素的频率，并根据不同情况（如三个数相同、两个数相同等）进行细致的条件判断，以确定是否构成满足条件的三元组。
难度
- 边界条件处理：需要考虑数组为空、数组中元素过少以及所有元素同号等边界情况，确保算法的正确性和鲁棒性。
- 优化与细节：在实现过程中，如何在保证正确性的前提下进行优化，如减少不必要的计算和比较，是具有一定难度的。例如，在排序 + 双指针法中，合理地跳过重复元素可以避免大量无效计算；在统计频率 + 双指针法中，精确的条件判断可以避免遗漏或重复计算三元组。
扩展及难度加深题目
扩展题目1：四数之和
给定一个包含 (n) 个整数的数组 nums 和一个目标值 target，找出数组中所有满足 (a + b + c + d = target的唯一四元组(a, b, c, d)`。可以类比三数之和的方法，通过排序后使用双指针法或其他优化策略来解决，时间复杂度可能达到 (O(n^3))。
扩展题目2：带权重的三数之和
给数组中的每个元素赋予一个权重，要求找出满足三数之和为 0 的三元组，并且使得三元组的权重之和最大（或最小）。这需要在寻找三元组的过程中，同时考虑权重因素，增加了算法的复杂性。
难度加深题目1：动态更新数组的三数之和
假设数组会动态更新（添加或删除元素），要求在每次更新后能够高效地更新满足三数之和为 0 的三元组集合。这可能需要使用更复杂的数据结构（如平衡二叉搜索树）来维护数组元素，以便在更新后快速重新计算结果。
难度加深题目2：多维数组的三数之和
给定一个多维数组（如二维数组，每个元素又是一个数组），要求在这些数组中找出所有满足三数之和为 0 的组合。这需要考虑如何遍历多维数组，并在不同维度上应用类似的算法思想。
应用场合
- 组合优化问题：在资源分配、任务调度等场景中，可能需要从多个资源或任务的参数中找出特定组合，使得它们的和满足某个条件，类似于三数之和问题。
- 数据分析与挖掘：在数据分析中，可能需要从一组数据中找出满足特定数值关系的组合，以发现潜在的模式或规律。例如，在金融数据中，寻找满足特定资金流动关系的交易组合。
- 算法竞赛与面试：此类问题作为经典的算法问题，常用于算法竞赛和面试中，考察应聘者对数组操作、排序算法、双指针法以及去重等技术的掌握和应用能力。
