leetcode 15. 3Sum (k-sum问题,two pointer)

Posted by 111qqz on Thursday, April 13, 2017

TOC

Given an array S of n integers, are there elements a, b, c in S 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.

思路:排序O(nlgn),然后枚举一个元素O(n),对于每个元素,在剩下的区间中 two pointer O(n)

整体复杂度 O(n^2)。

hash的解法以后补。

/* ***********************************************
Author :111qqz
Created Time :2017年04月13日 星期四 16时07分00秒
File Name :15.cpp
************************************************ */
class Solution {
public:
    set<vector<int> >se;
    vector<vector<int> >res;
    vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(),nums.end());
    int n = nums.size();
    for ( int i = 0 ; i <=n-3 ; i++)
    {
        int head = i+1;
        int tail = n-1;
        int tar = -nums[i];
        while (head<tail)
        {
        if (nums[head]+nums[tail]==tar)
        {
            vector<int>tmp;
            tmp.push_back(nums[i]);
            tmp.push_back(nums[head]);
            tmp.push_back(nums[tail]);
            se.insert(tmp);
            head++;
            tail--;
        }
        else if (nums[head]+nums[tail]<tar) head++;
        else tail--;
        }
    }
    for ( auto &it : se)
        res.push_back(it);
    return res;
    }
};

「真诚赞赏,手留余香」

111qqz的小窝

真诚赞赏,手留余香

使用微信扫描二维码完成支付