[array] leetCode-18. 4Sum -Medium

18. 4Sum -Medium

descrition

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]

]

解析

与 3Sum 的思路一样。不过代码量一大要 bug free 还真得细心一些！！

code



#include <iostream>

#include <vector>

#include <algorithm>

#include <limits>

using namespace std;

class Solution{

public:

	int threeSumClosest(vector<int>& nums, int target){

		sort(nums.begin(), nums.end()); // ascending

		int min_gab = numeric_limits<int>::max();

		int ans = target;

		for(int i=0; i<nums.size(); i++){

			int target_local = target - nums[i];

			int ileft = i + 1;

			int iright = nums.size() - 1;

			while(ileft < iright){ // two pointer searching

				int sum = nums[ileft] + nums[iright];

				if(sum == target_local) // right answer

					return target;

				if(sum < target_local) // move ileft to increase sum

					ileft++;

				else // sum > target_local

					iright--;

				int gab = abs(sum - target_local);

				if(gab < min_gab){

					ans = sum + nums[i];

					min_gab = gab;

				}

			}

		}

		return ans;

	}

};

int main()

{

	return 0;

}

巴特西

[array] leetCode-18. 4Sum -Medium

18. 4Sum -Medium

descrition

解析

code

最新文章

热门文章