原题

LintCode 58. 4Sum

Description

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.

Notice

Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
The solution set must not contain duplicate quadruplets.

Example

Given array S = {1 0 -1 0 -2 2}, and target = 0. A solution set is:

(-1, 0, 0, 1)
(-2, -1, 1, 2)
(-2, 0, 0, 2)

解题

可以借鉴3Sum的思路。

代码

class Solution {
public:
    /*
    * @param numbers: Give an array
    * @param target: An integer
    * @return: Find all unique quadruplets in the array which gives the sum of zero
    */
    vector<vector<int>> fourSum(vector<int> numbers, int target) {
        // write your code here
        set<vector<int>> ans;
        sort(numbers.begin(), numbers.end());
        for (int i = 0; i < int(numbers.size() - 3); i++) {
            for (int j = i + 1; j < int(numbers.size() - 2); j++) {
                int left = j + 1;
                int right = numbers.size() - 1;
                while (left < right && left < numbers.size() - 1) {
                    int sum = numbers[i] + numbers[j] + numbers[left] + numbers[right];
                    if (sum == target) {
                        ans.insert(vector<int>({ numbers[i], numbers[j], numbers[left], numbers[right] }));
                        left++;
                        right++;
                    } else if (sum > target) {
                        right--;
                    } else {
                        left++;
                    }
                }
            }
        }
        return vector<vector<int>>(ans.begin(), ans.end());
    }
};