LeetCode 15. 3Sum (三数之和)

超、凢脫俗 2022-05-11 00:20 157阅读 0赞

题目描述：

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

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

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
    
    满足要求的三元组集合为：
    [
      [-1, 0, 1],
      [-1, -1, 2]
    ]

Accepted C++ Solution:

class Solution {
    public:
        vector<vector<int>> threeSum(vector<int>& nums) {
            vector< vector<int> > res;
            std::sort(nums.begin(), nums.end());    //先将数组变为有序的
            
            for (int i = 0; i < nums.size(); i++) {
                int target = -nums[i];
                int front = i+1;
                int back = nums.size() - 1;
                
                while(front < back) {
                    int sum = nums[front] + nums[back];
                    
                    if (sum < target)
                        front++;
                    
                    else if (sum > target)
                        back--;
                    
                    else {
                        vector<int> solu(3,0);
                        solu[0] = nums[i];
                        solu[1] = nums[front];
                        solu[2] = nums[back];
                        res.push_back(solu);
                        
                        while(front < back && nums[front] == solu[1])   front++;    //跳过重复元素
                        while(front < back && nums[back] == solu[2])    back--;    //跳过....
                    }
                }
                while(i+1 < nums.size() && nums[i+1] == nums[i])    //跳过重复元素
                    i++;
            }
            return res;
        }
    };