三数之和

发布于 2020-07-16 07:42:07   阅读量 69  点赞 0  

原题地址:https://leetcode-cn.com/problems/3sum/

题目

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


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


示例:

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

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



解法

 对于m数相加(匹配)问题,使用排序+双指针减少一层迭代,将枚举法的时间复杂度降至 O(n^{m-1})


代码

vector<vector<int>> Solution::threeSum(vector<int> &nums) {
    int len = nums.size();
    vector<vector<int>> result = vector<vector<int>>();

    if(len<3){
        return result;
    }

    quickSort(nums,0,len-1);

    for(int i=0;i<len-2;i++){
        if(i>0&&nums[i-1]==nums[i]){
            continue;
        }

        int start = i+1;
        int end = len-1;

        while(start<end){
            int sum = nums[i] + nums[start] + nums[end];
            if(sum==0){
                vector<int> vec = {nums[i],nums[start],nums[end]};
                result.push_back(vec);
                start++;
                end--;

                // 排除寻找第二、三个元素时,重复元素带来的重复解
                while(start<end&&nums[start]==nums[start-1]){
                    start++;
                }
                while(start<end&&nums[end]==nums[end+1]){
                    end--;
                }
            }else if(sum<0){
                start++;
            }else{
                end--;
            }
        }
    }
    return result;
}


Last Modified : 2020-09-27 01:30:19