【逐日一题】LeetCode - 三数之和

给你一个整数数组 nums ，判定是否存在三元组 [nums, nums[j], nums[k]] 满意 i != j、i != k 且 j != k ，同时还满意 nums + nums[j] + nums[k] == 0 。请你返回全部和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例

示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：满意条件的三元组为 [-1, 0, 1] 和 [-1, -1, 2]。
示例 2：
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。
示例 3：
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0。
思绪分析

这个问题的焦点思绪是找到数组中的三个数，其和为 0，同时要避免重复的组合。为了解决这个问题，我们可以通过排序和双指针的联合来有用地实现。
步骤：

• 排序数组：首先将 nums 数组按升序排序，便于后续使用双指针探求满意条件的三元组。
  
• 遍历数组：固定一个数，然后使用双指针在剩余的部分查找满意条件的两个数。
  
• 避免重复：
  
  
  
  • 假如当前固定的数和前一个数相同，可以直接跳过，以避免重复三元组。
    
  • 双指针过程中，若左右指针指向的数值和前一个数相同，同样跳过。
    
  
  

这个思绪使得代码在处理每个三元组时，只计算不重复的组合。
实当代码

1. class Solution {
2. public:
3.     vector<vector<int>> threeSum(vector<int>& nums) {
4.         vector<vector<int>> ans;
5.         sort(nums.begin(), nums.end());  // 第一步：排序数组
6.         for(int a = 0; a < nums.size(); a++) {
7.             if(nums[a] > 0) break;  // 如果当前数大于0，跳出循环，因为后面的数都更大，不可能和为0
8.             if(a > 0 && nums[a] == nums[a - 1]) continue;  // 避免重复
10.             // 初始化双指针
11.             int left = a + 1, right = nums.size() - 1;
12.             while(left < right) {
13.                 int sum = nums[a] + nums[left] + nums[right];
14.                 if(sum == 0) {
15.                     ans.push_back({nums[a], nums[left], nums[right]});
16.                     // 移动指针避免重复
17.                     while(left < right && nums[left] == nums[left + 1]) left++;
18.                     while(left < right && nums[right] == nums[right - 1]) right--;
19.                     left++;
20.                     right--;
21.                 } else if(sum < 0) {
22.                     left++;
23.                 } else {
24.                     right--;
25.                 }
26.             }
27.         }
28.         return ans;
29.     }
30. };

复制代码

代码讲解

• 排序：sort(nums.begin(), nums.end()); 这一步可以简化后续查找过程，因为排序后的数组让双指针查找更有用率。
  
• 外层循环：遍历数组 nums，每次固定一个数 nums[a]。当 nums[a] > 0 时，直接退出循环，因为在排序数组中，后续数值都更大，无法达到 0。
  
• 双指针：对于每个固定数，用双指针在剩余部分查找两数之和为 -nums[a] 的组合。
  
  
  
  • 假如找到和为 0 的组合，将三元组加入结果集中。
    
  • 移动指针时检查是否有重复数，如有则跳过，以避免重复解。
    
  
  

时空复杂度分析

• 时间复杂度：O(n^2)
  
  
  
  • 外层循环复杂度为 O(n)，双指针查找复杂度为 O(n)，因此总体复杂度为 O(n^2)。
    
  
  
• 空间复杂度：O(log(n)) 或 O(n)，取决于排序算法的实现方式。返回结果不计入空间复杂度。
  

比较其他实现方式

一种直接的实现方式是三重循环，但这样会导致 O(n^3) 的时间复杂度，效率低下。而双指针配合排序的实现方法可以有用地淘汰时间复杂度到 O(n^2)，在大数据量情况下具有显著的性能优势。
总结

通过排序和双指针联合，我们可以高效地解决三数之和问题。该方法不但能避免重复，还能在 O(n^2) 的时间内找到全部符合条件的三元组，是一种简洁且高效的解法。
暴力破解实现

除了使用双指针的方法，我们还可以采用暴力破解的方法来解决这个问题。暴力破解的思绪就是通过三重循环罗列全部可能的三元组，检查其和是否为零。固然这种方法简单易懂，但效率较低。下面是暴力破解的实当代码：

1. class Solution {
2. public:
3.     vector<vector<int>> threeSum(vector<int>& nums) {
4.         vector<vector<int>> ans;
5.         for (int i = 0; i < nums.size(); i++) {
6.             for (int j = i + 1; j < nums.size(); j++) {
7.                 for (int k = j + 1; k < nums.size(); k++) {
8.                     if (nums[i] + nums[j] + nums[k] == 0) {
9.                         vector<int> triplet = {nums[i], nums[j], nums[k]};
10.                         // 检查三元组是否已存在于答案中
11.                         if (find(ans.begin(), ans.end(), triplet) == ans.end()) {
12.                             ans.push_back(triplet);
13.                         }
14.                     }
15.                 }
16.             }
17.         }
18.         return ans;
19.     }
20. };

复制代码

代码讲解

• 三重循环：外层循环遍历第一个数，内层循环遍历第二个和第三个数。
  
• 条件判定：检查三个数的和是否为零，假如满意条件则将三元组加入结果集中。
  
• 避免重复：在加入结果集之前，使用 find 函数检查该三元组是否已经存在。
  

时空复杂度分析

• 时间复杂度：O(n^3)
  
  
  
  • 三重循环的实现方式使得时间复杂度达到 O(n^3)，当 n 较大时，效率非常低下。
    
  
  
• 空间复杂度：O(n)，用于存储结果集，最坏情况下会生存全部三元组。
  

总结比较

暴力破解法固然简单直观，但对于大规模数据，效率低下。而通过排序与双指针的方法，可以将时间复杂度降低至 O(n^2)，适用于大数据场景。因此，在实际应用中，保举使用双指针的方法解决三数之和问题。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。