LeetCode 4sum

リンク:https://oj.leetcode.com/problems/4sum/
1つの方法は,3 sumと同様にヘッドテールポインタを用いて交互に移動し,時間的複雑度をO(n 3),空間的複雑度をO(1)とし,注意を払うことである.

class Solution
{
	public:
		vector<vector<int> >fourSum(vector<int> &num,int target)
		{
			vector<vector<int> > ans;
			sort(num.begin(),num.end());
			int n=num.size();
			for(unsigned int i=0;i<n;i++)
			{
			    if(i > 0 && num[i] == num[i-1])
                    continue;
				for(unsigned int j=i+1;j<n;j++)
				{
				    if(j > i + 1 && num[j] == num[j-1])
                        continue;
					int st=j+1,en=n-1;
					while(st<en)
					{
					    if(st>j+1&&num[st]==num[st-1])
					    {
					        st++;
					        continue;
					    }
					    if(en<n-1&&num[en]==num[en+1])
					    {
					        en--;
					        continue;
					    }
						int sum=num[i]+num[j]+num[st]+num[en];
						if(sum>target)
							en--;
						if(sum<target)
							st++;
						if(sum==target)
						{
							vector<int> tem;
							tem.push_back(num[i]);
							tem.push_back(num[j]);
							tem.push_back(num[st]);
							tem.push_back(num[en]);
							ans.push_back(tem);
							tem.clear();
							st++;
							en--;
						}

					}
				}
			}

			return ans;
		}
};

もう1つの比較的効率的な方法は、空間の複雑さを犠牲にして時間の複雑さを取り替えることです.
ハッシュテーブルを使用してすべての要素の2つの和を格納し、2 sumを1回作成します.
また,2 sumは線形アルゴリズムがある:すべての要素をハッシュテーブルのように配置し,ハッシュテーブルによりtarget−numが存在するか否かを判断するが,ハッシュテーブルを利用しているため,判断のたびに定数レベルの時間しかかからない.
重さを落とすならsetも考えられます