LeetCode--3Sum

发表于 | 分类于 |

题目描述：

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

note:

The solution set must not contain duplicate triplets.

样例：

1
2
3
4
5
6
7
Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

题意：

给你 n 个数，要找出三个不同的数相加为 0，并返回这三个数

思路：

对数组排序，然后遍历。

在遍历到正数的时候，因为数组是有序的，后面的数也全是正数，那么就永远不可能相加为 0，所以后面的数字就不需要再进行遍历。

同时，还会有重复的数值出现，所以当遍历到重复的元素的时候，就跳过。

在对于遍历到的数，用 0 减去当前遍历的数得到一个 target，然后就只需要在当前数之后找到两数之和为 target 的两个数即可。

我的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        sort(nums.begin(), nums.end());
        int n = nums.size();
        if(n == 0 || nums.back() < 0 || nums.front() > 0) return res;
        for(int i = 0; i < n; ++i){
            if(nums[i] > 0) break;
            if(i > 0 && nums[i] == nums[i - 1]) continue;
            int target = 0 - nums[i];
            int l = i + 1, r = nums.size() - 1;
            while(l < r){
                if(nums[l] + nums[r] == target){
                    res.push_back({nums[i], nums[l], nums[r]});
                    /* 去除重复元素，防止重复答案的产生 */
                    while(l < r && nums[l] == nums[l + 1]) ++l;
                    while(l < r && nums[r] == nums[r - 1]) --r;
                    ++l; --r;
                }
                else if(nums[l] + nums[r] > target) --r;
                else ++l;
            }
        }
        return res;
    }
};

Runtime：112ms Memory：16.2MB