leetcode15 三数之和

1.哈希法

为了避免重复

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {set<vector<int>> temple;//使用 set 来存储符合条件的三元组，避免重复vector<vector<int>> out;//存放最终输出结果sort(nums.begin(),nums.end());//先进行数组排序for(int i = 0; i < nums.size(); i++){if(i > 0 && nums[i] == nums[i-1]) continue;//如果当前数值与上一轮循环所得数值相同、后续找到的三元组将相同，没必要再找，退出本轮unordered_set<int> hash;//定义哈希表存放待查找内容for(int j = i+1; j < nums.size(); j++){                if(hash.find(-(nums[i] + nums[j])) != hash.end()){temple.insert({nums[i], nums[j], -(nums[i] + nums[j])});//哈希表中存在与当前nums[i]\nums[j]匹配的值 -(nums[i] + nums[j])，即找到了符合条件的三元组将其存入                 }hash.insert(nums[j]);//将nums[j]存入，可能成为后续寻找的-(nums[i] + nums[j])值}    }for(const auto& t: temple){out.push_back(t);}//遍历三元组将他们存入最终输出的变量中return out;}
};

在解决 三数之和（3Sum）问题时，先对数组进行排序是一个非常重要的步骤。排序不仅简化了问题的解决过程，还能帮助我们高效地处理重复元素和优化查找逻辑。以下是详细解释：

1. 排序的作用

（1）方便去重

• 排序后，相同的元素会相邻排列。这样，我们可以通过简单的条件判断（如 nums[i] == nums[i - 1]）来跳过重复的元素，避免重复解。

• 例如，数组 [-1, -1, 0, 1, 2] 中，两个 -1 相邻，可以通过判断 nums[i] == nums[i - 1] 来跳过第二个 -1。

（2）简化查找逻辑

• 排序后，数组是有序的，可以利用 双指针法 来高效查找满足条件的三元组。

• 双指针法的时间复杂度是 O(n)O(n)，而哈希法的时间复杂度是 O(n2)O(n2)，因此排序后使用双指针法可以显著提高性能。

（3）确保结果有序

• 排序后，找到的三元组 (nums[i], nums[j], nums[k]) 也是有序的，这样可以避免重复解（如 [-1, 0, 1] 和 [0, -1, 1] 被视为不同的解）。

---

在内层循环中，哈希表的作用是存储已经遍历过的 nums[j]。每次遍历到一个新的 nums[j] 时：

• 先检查哈希表中是否存在 target = -nums[i] - nums[j]。

  • 如果存在，说明 nums[i] + nums[j] + target = 0，即找到一个三元组。

• 然后将当前的 nums[j] 加入哈希表，以便后续的 nums[j] 可以使用它来查找目标值。

nums[i] 是外层循环的固定值，它不会被用作目标值（target），因为 target 的定义是 -nums[i] - nums[j]。

去重逻辑

• 在外层循环中，通过 if (i > 0 && nums[i] == nums[i - 1]) continue; 跳过重复的 nums[i]。

• 在内层循环中，哈希表会自动处理重复的 nums[j]，因为哈希表的特性是存储唯一的键。

• const auto& triplet：

  • auto：自动推导变量类型。在这里，triplet 的类型是 const vector<int>&。

  • const：表示 triplet 是只读的，不能修改。

  • &：表示引用，避免拷贝 vector<int>，提高效率。

2.双指针法

先排序，有一层for循环，定义指针i从下标0的地方开始，同时定一个下标left 定义在i+1的位置上，定义下标right 在数组结尾的位置上。

接下来如何移动left 和right呢， 如果nums[i] + nums[left] + nums[right] > 0 就说明 此时三数之和大了，因为数组是排序后了，所以right下标就应该向左移动，这样才能让三数之和小一些。如果 nums[i] + nums[left] + nums[right] < 0 说明 此时 三数之和小了，left 就向右移动，才能让三数之和大一些，直到left与right相遇为止。

问题分析

1. sum 的计算位置：

   • 你在外层循环中计算了 sum = nums[i] + nums[left] + nums[right]，但在内层循环中 left 和 right 会变化，sum 的值却没有更新，导致逻辑错误。

2. 去重逻辑：

   • 你在找到满足条件的三元组后，没有跳过重复的 nums[left] 和 nums[right]，这可能导致重复解。(没找到三元组的时候无需去重）

3. set 的使用：

   • 你使用 set<vector<int>> 来存储结果，虽然可以避免重复解，但效率较低，因为 set 的插入操作是 O(log⁡n)O(logn) 的。

4. 边界条件：

   • 你没有处理数组长度小于 3 的情况。

class Solution{
public:vector<vector<int>> threeSum(vector<int>& nums){sort(nums.begin(), nums.end());vector<vector<int>> out;if (nums.size() < 3) {return out;}for(int i = 0; i < nums.size(); i++){if(i > 0 && nums[i] == nums[i - 1]) continue;int left = i + 1, right = nums.size() - 1;while(left<right){int sum = nums[i] + nums[left] + nums[right];if(sum > 0){right --;}if(sum < 0){left ++;}if(sum == 0){out.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;right --;left ++;}} }return out;}
};