题目

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

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

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：[[-1, 0, 1], [-1, -1, 2]]

来源：力扣（LeetCode）

题解

这道题可以使用遍历+双指针扫描法进行，并加入一定的剪枝优化。

这个办法的精髓在于数组的预处理——排序。排序好了的数组将会对扫描有非常大的帮助。

遍历+双指针扫描

这里有两部分，第一部分是遍历，第二部分是双指针。遍历指的是指遍历一个数作为参照主体。双指针是指以参照主体为参照，对参照主体之后的部分进行一头一尾两个指针向中间扫描。

剪枝

这一套扫描法中，可以有三个位置进行剪枝操作。

剪枝1：

对排序好的数组本身进行分析：
如果数组为：空、个数小于3、第一个数大于0、最后一个数小于0，即代表无法完成三数之和等于0。

剪枝2：

对“遍历”操作进行剪枝：
如果参照主体本身大于0，则代表右侧所有的元素均大于参照主体本身，即为无法完成三数之和大于0，直接结束遍历（break）。

剪枝3：

对“遍历”操作进行剪枝：
如果当前的参照主体与前一个参照主体相等，则代表此参照主体经过相同数组查找出来的“三数之和”结果与之前必定相同，所以可以直接跳过本参照主体（continue）。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ivvec;
        int n = nums.size();
        
        // 排序，排序之后的数组会好用很多
        sort(nums.begin(), nums.end());
        
        // 剪枝：
        // 数组空 || 数字个数小于3 || 排序好的数字第一个大于0 || 排序好的最后一个小于0
        if (nums.empty() || n < 3 || nums.front() > 0 || nums.back() < 0) {
            return ivvec;
        }
        
        for (int i = 0; i < n; ++i) {
            int fix = nums[i];
            
            // 剪枝：
            // 从大到小排序好的数组，如果扫描进行到了大于0的位置了，那就可以结束了
            if (fix > 0)
                break;
            
            // 剪枝：
            // 如果目前进行的数字与前一个相同，则与之对应的结果必定必定相同
            if (i > 0 && fix == nums[i - 1]) continue;
            
            // 双指针法
            int l = i + 1, r = n - 1;
            while (l < r) {
                int sum = nums[l] + nums[r];
                if (sum == -fix) {
                    if (l == i + 1 || r == n - 1) {
                        ivvec.push_back(vector<int>{fix, nums[l], nums[r]});
                        ++l, --r;
                    } else if (nums[l] == nums[l - 1]) {
                        ++l;
                    } else if (nums[r] == nums[r + 1]) {
                        --r;
                    } else {
                        ivvec.push_back(vector<int>{fix, nums[l], nums[r]});
                        ++l, --r;
                    }
                } else if (sum < -fix) {
                    ++l;
                } else {
                    --r;
                }
            }
        }
        
        return ivvec;
    }
};

结果

执行用时 : 144 ms, 在所有 C++ 提交中击败了85.23%的用户
内存消耗 : 14.5 MB, 在所有 C++ 提交中击败了95.53%的用户