【力ボタンLeetCode】15三数の和

タイトル説明(難易度中)
n個の整数を含む配列numsを与え,numsにa,b,cの3つの要素が存在するか否かを判断し,a+b+c=0とする.条件を満たし、繰り返さないすべての三元グループを見つけます.
注意:答えに重複する三元グループは含まれてはいけません.
例えば、所与の配列nums=[−1,0,1,2,−1,−4],
要求を満たす三元群の集合は,[[−1,0,1],[−1,−1,2]]である.
リンク
https://leetcode-cn.com/problems/3sum/
構想
1、暴力列挙、タイムアウト2、ソート後、二重ポインタで衝突し、重さを落とす3、元の配列を前処理し、0は3つ保留し、その他は最大2つ保留4、mapでカウントした3つに分けて異なり、2つ同じ、3つの0、3つの状況討論がある
コード#コード#
ソート後のダブルポインタ:(setコレクションで重み付け)

class Solution {
public:
    vector<vector<int> > threeSum(vector<int>& nums) {
    	set<vector<int> > ansTemp;
    	vector<vector<int> > ans;
    	if(nums.size() < 3){
    		return ans;
    	}
        sort(nums.begin(), nums.end());
        vector<int> tnums;
        //         
        int lnum1, lnum2, lnum3;
        tnums.push_back(nums[0]);
        tnums.push_back(nums[1]);
        tnums.push_back(nums[2]);
        lnum1 = nums[0];
        lnum2 = nums[1];
        lnum3 = nums[2];
        for(int i = 3; i < nums.size(); i++){
        	if(nums[i] != lnum1 || nums[i] != lnum2 || nums[i] != lnum3){
        		tnums.push_back(nums[i]);
        		lnum1 = lnum2;
        		lnum2 = lnum3;
        		lnum3 = nums[i];
        	}
        }
        for(int i = 1; i < tnums.size()-1; i++){
        	//           
        	if(tnums[i] < 0 && tnums[i] == tnums[i+1]){
        		continue;
        	}
        	if(tnums[i] > 0 && tnums[i] == tnums[i-1]){
        		continue;
        	}
        	int l = 0;
        	int r = tnums.size() - 1;
        	while(l < i && i < r){
        		if(tnums[l] + tnums[r] + tnums[i] == 0){
        			vector<int> t;
        			t.push_back(tnums[l]);
        			t.push_back(tnums[i]);
        			t.push_back(tnums[r]);
        			ansTemp.insert(t);
        			l++;
        			r--;
        		}
        		else if(tnums[l] + tnums[r] + tnums[i] > 0){
        			r--;
        		}
        		else{
        			l++;
        		}
        	}
        }
        ans.assign(ansTemp.begin(), ansTemp.end());
        return ans;
    }
};

並べ替え後の二重ポインタ:(ルールで重さを除く)中間点選択ソート後の配列について、0未満の数を選択し、右端のものを選択します.0より大きい数が必要です.ソート後の配列について、0より大きい数を選択します.左端のものを選択します.0より小さい数が必要です.ソート後の配列について、0に等しい場合、2つの0を超える場合、中間の0を選択します.その他の場合、任意に選択します.1つの0はこのようにして重複しないことを保証することができます

class Solution {
public:
    vector<vector<int> > threeSum(vector<int>& nums) {
    	set<vector<int> > ansTemp;
    	vector<vector<int> > ans;
    	if(nums.size() < 3){
    		return ans;
    	}
        sort(nums.begin(), nums.end());
        vector<int> tnums;
        int lnum1, lnum2, lnum3;
        tnums.push_back(nums[0]);
        tnums.push_back(nums[1]);
        tnums.push_back(nums[2]);
        lnum1 = nums[0];
        lnum2 = nums[1];
        lnum3 = nums[2];
        for(int i = 3; i < nums.size(); i++){
        	if(nums[i] != lnum1 || nums[i] != lnum2 || nums[i] != lnum3){
        		tnums.push_back(nums[i]);
        		lnum1 = lnum2;
        		lnum2 = lnum3;
        		lnum3 = nums[i];
        	}
        }
        for(int i = 1; i < tnums.size()-1; i++){
        	if(tnums[i] == 0 && tnums[i-1] == 0 && tnums[i+1] == 0){
        	
        		vector<int> t;
        		t.push_back(0);
        		t.push_back(0);
        		t.push_back(0);
        		ans.push_back(t);
        		continue;
        	}
        	if(tnums[i] <= 0 && tnums[i] == tnums[i+1]){
        		continue;
        	}
        	if(tnums[i] > 0 && tnums[i] == tnums[i-1]){
        		continue;
        	}
        	int l = 0;
        	int r = tnums.size() - 1;
        	while(l < i && i < r){
        		if(tnums[l] + tnums[r] + tnums[i] == 0){
        			vector<int> t;
        			t.push_back(tnums[l]);
        			t.push_back(tnums[i]);
        			t.push_back(tnums[r]);
        			ans.push_back(t);
        			l++;
        			while(l < i && tnums[l] == tnums[l-1]){
        				l++;
        			}
        			r--;
        			while(r > i && tnums[r] == tnums[r+1]){
        				r--;
        			}
        		}
        		else if(tnums[l] + tnums[r] + tnums[i] > 0){
        			r--;
        			while(r > i && tnums[r] == tnums[r+1]){
        				r--;
        			}
        		}
        		else{
        			l++;
        			while(l < i && tnums[l] == tnums[l-1]){
        				l++;
        			}
        		}
        	}
        }
        return ans;
    }
};

状況別特殊処理:(実践証明が遅い)

class Solution {
public:
    vector<vector<int> > threeSum(vector<int>& nums) {
    	vector<vector<int> > ans;
    	map<int, int> tm;
    	for(int i = 0; i < nums.size(); i++){
    		if(tm.count(nums[i]) == 0){
    			tm[nums[i]] = 1;
    		}
    		else{
    			tm[nums[i]] += 1;
    		}
    	}
    	//         ，   0
		if(tm.count(0) != 0 && tm.find(0)->second >= 3){
			vector<int> t;
			t.push_back(0);
			t.push_back(0);
			t.push_back(0);
			ans.push_back(t);
		} 
		//         
		map<int, int>::iterator iter;
		for(iter = tm.begin(); iter != tm.end(); iter++){
			if(iter->second >= 2 && iter->first != 0){
				if(tm.count(0-iter->first*2) > 0){
					vector<int> t;
					t.push_back(iter->first);
					t.push_back(iter->first);
					t.push_back(0-iter->first*2);
					ans.push_back(t);
				}
			}
		} 
		//          
		vector<int> tnums;
		map<int, int> tn;
		for(iter = tm.begin(); iter != tm.end(); iter++){
			tnums.push_back(iter->first);
		}
		for(int i = 0; i < tnums.size(); i++){
			tn[tnums[i]] = i;
		}
		for(int i = 0; i < tnums.size(); i++){
			for(int j = i+1; j <tnums.size(); j++){
				int temp = 0 - tnums[i] - tnums[j];
				if(tm.count(temp) > 0 && tn[temp] > j){
					vector<int> t;
					t.push_back(tnums[i]);
					t.push_back(tnums[j]);
					t.push_back(temp);
					ans.push_back(t);
				}
			}
		}
        return ans;
    }
};