LeetCode高频面试题解析：三数之和的完美解法

一、问题分析

三数之和问题要求我们在一个整数数组中找到所有不重复的三元组，使得这三个数的和等于0。这是一个经典的双指针问题，需要特别注意去重处理。

二、解决方案思路

1. ‌排序‌：首先对数组进行排序，这样我们可以利用有序性来优化搜索过程。

2. ‌固定一个数‌：遍历数组，每次固定一个数作为三元组的第一个元素。

3. ‌双指针搜索‌：对于固定的第一个数，使用双指针在剩余部分寻找另外两个数，使得三数之和为0。

4. ‌去重处理‌：在每一步都需要跳过重复元素，避免产生重复的三元组。

三、C++代码实现

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
    int n = nums.size();
   
    // 1. 首先对数组进行排序
    sort(nums.begin(), nums.end());
   
    // 2. 遍历数组，固定第一个数
    for (int i = 0; i < n - 2; ++i) {
        // 跳过重复的第一个数
        if (i > 0 && nums[i] == nums[i - 1]) continue;
       
        int left = i + 1;    // 左指针从i+1开始
        int right = n - 1;   // 右指针从末尾开始
        int target = -nums[i]; // 需要找到两数之和等于-target
       
        // 3. 双指针搜索
        while (left < right) {
            int sum = nums[left] + nums[right];
           
            if (sum == target) {
                // 找到有效三元组
                result.push_bACk({nums[i], nums[left], nums[right]});
               
                // 跳过重复的left和right
                while (left < right && nums[left] == nums[left + 1]) ++left;
                while (left < right && nums[right] == nums[right - 1]) --right;
               
                // 移动指针继续搜索
                ++left;
                --right;
            } else if (sum < target) {
                // 和太小，左指针右移
                ++left;
            } else {
                // 和太大，右指针左移
                --right;
            }
        }
    }
   
    return result;
    }
};

四、边界情况考虑

• 数组长度小于3时直接返回空结果

• 所有数都大于0时可以直接返回空结果（优化点）

• 处理重复元素时要小心指针越界