leetcode 18. 4Sum (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, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note: The solution set must not contain duplicate quadruplets.

思路: O(n^2)枚举两个元素,变成2-sum问题,总体复杂度O(n^3)

hash的解法以后补

/* ***********************************************
Author :111qqz
Created Time :2017年04月13日 星期四 17时24分54秒
File Name :18.cpp
************************************************ */
class Solution {

public:
    
    vector<vector<int> >res;
    set<vector<int> >se;
    int n;
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
    n = nums.size();
    if (n<4) return res;
    sort(nums.begin(),nums.end());
	
    for ( int i = 0 ; i <= n-4 ; i++ )
    {
        for ( int j = i+1 ; j <= n-3 ; j++)
        {
        int head = j+1;
        int tail = n-1;
        int tar = target - nums[i] - nums[j];
        while (head<tail)
        {
            if (nums[head]+nums[tail]==tar)
            {
            vector<int>tmp;
            tmp.push_back(nums[i]);
            tmp.push_back(nums[j]);
            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的小窝

真诚赞赏,手留余香

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