leetcode 18. 四数之和

class Solution {
public:
	vector<vector<int>> fourSum(vector<int>& nums, int target) 
	{
		//获取当前数组的长度
		int size = nums.size();
		//构造存储所有结果的数组
		vector<vector<int>> ret;
		//如果当前数组长度小于4,直接返回空容器
		if (size < 4) return ret;
		//给数组排序
		sort(nums.begin(),nums.end());
		for (int i = 0; i < size-3; i++)
		{
			if (i > 0 && nums[i] == nums[i - 1]) continue;//第一个固定指针去重
			for (int j = i + 1; j < size-2; j++)
			{
				if (j > i+1 && nums[j] == nums[j - 1]) continue;//第二个指针固定去重
				int p = j + 1, q = size - 1;//前后两个指针
				while (p < q)
				{
					int sum = nums[i] + nums[j] + nums[p] + nums[q];
					if (sum < target)//和小了，为了增大和，前指针往后移动
						while (p < q && nums[p] == nums[++p]);//如果前指针后移出现重复数字就一直后移，直到没有出现重复元素为止，否则只移动一次
					else if (sum > target)//和大了，后指针前移
						while (p < q && nums[q] == nums[--q]);//同上
					else
					{
						ret.push_back({ nums[i],nums[j],nums[p],nums[q] });
						//前指针后移，后指针前移继续寻找当前固定k值下的可能解
				      //同上，没有出现重复解，移动一次
						while (p < q && nums[p] == nums[++p]);
						while (p < q && nums[q] == nums[--q]);
					}
				}
			}
		}
		return ret;
	}
};

class Solution {
	vector<vector<int>> ret;
	vector<int> mynums,subans;
	int tar, numSize;//tar:目标值  numSize:数组大小
public:
	vector<vector<int>> fourSum(vector<int>& nums, int target) 
	{
        sort(nums.begin(), nums.end());
		//获取当前数组的长度
		numSize = nums.size();
		mynums = nums;
		tar = target;
		if (numSize < 4) return ret;
		DFS(0,0);
		return ret;
	}
	void DFS(int low, int sum)//low: 起始遍历的下标  sum:当前需要凑出的目标值
	{
		//找到一个解
		if (sum == tar && subans.size() == 4)
		{
			ret.push_back(subans);
			return;
		}
		//寻找可能解
		for (int i = low; i < numSize; i++)
		{
			//剪枝:当前需要找的剩余元素个数比剩余元素多，那么说明无解，返回
			if (numSize - i <4 - subans.size()) return;
			if (i > low && mynums[i] == mynums[i - 1]) continue;//去重
			//第三种情况的剪枝
			if (i<numSize - 1 && sum + mynums[i] + mynums[i + 1] * (int)(3- subans.size())>tar) return;
			//第四种情况的剪枝
			if (i < numSize - 1 && sum + mynums[i] + mynums[numSize-1] * (int)(3 - subans.size()) < tar) continue;
			//确定一个位置
			subans.push_back(mynums[i]);
			//去确定下一个位置
			DFS(i + 1, sum + mynums[i]);
			//回溯，寻找其他解
			subans.pop_back();
		}
	}
};

class Solution {
public:
	vector<vector<int>> fourSum(vector<int>& nums, int target) 
	{
		int size = nums.size();
		vector<vector<int>> ret;
		if (size < 4) return ret;
		sort(nums.begin(), nums.end());
		map<int, int> m;
		for (int i = 0; i < size; i++)
			m[nums[i]] = i;
		for (int i = 0; i < size - 3; i++)
		{
			if (i > 0 && nums[i] == nums[i-1]) continue;
			for (int j = i + 1; j < size - 2; j++)
			{
				if (j > i+1 && nums[j] == nums[j-1]) continue;
				for (int k = j + 1; k < size - 1; k++)
				{
					if (k > j+1 && nums[k] == nums[k-1]) continue;
					int c = target - nums[i] - nums[j] - nums[k];
					//当前数组中存在元素d,并且元素d下标大于元素c的下标
					if (m.find(c) != m.end())
					{
						if (m[c] > k)
							ret.push_back({ nums[i],nums[j],nums[k],c });
						else//首先当前已经不存在满足条件的元素d了，在往数组后面寻找元素c，c越大，需要的d越小，更不可能满足条件
							break;
					}

				}
			}
		}
        return ret;
	}
};