题目描述

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.

For 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] ]

思路

目的数组S中找出四个元素使之和为target，与3sum类似，只是外面变为了二重循环。

注意去重

代码

class Solution {public:	vector
    
     
       > fourSum(vector
      
       & nums, int target) {		int i, j;		vector
       
        
         > res;		if (nums.size() < 4)			return res;		sort(nums.begin(), nums.end());		if (nums.size() == 4)		{			if (nums[0] + nums[1] + nums[2] + nums[3] == target)			{				vector
         
           ini; ini.push_back(nums[0]); ini.push_back(nums[1]); ini.push_back(nums[2]); ini.push_back(nums[3]); res.push_back(ini); } else { } return res; } for (i = 0; i < nums.size() - 3; i++) { for (j = i + 1; j < nums.size() - 2; j++) { int k = j + 1; int l = nums.size() - 1; while (k < l) { if (nums[i] + nums[j] + nums[k] + nums[l] > target) { l--; } else if (nums[i] + nums[j] + nums[k] + nums[l] < target) { k++; } else if (nums[i] + nums[j] + nums[k] + nums[l] == target) { vector
          
            ini; ini.push_back(nums[i]); ini.push_back(nums[j]); ini.push_back(nums[k]); ini.push_back(nums[l]); res.push_back(ini); k++; l--; while (nums[k - 1] == nums[k]) k++; while (nums[l] == nums[l + 1]) l--; } } while (nums[j] == nums[j + 1]) j++; } while (nums[i] == nums[i + 1]) i++; } return res; }};复制代码