@LeetCode三数の和--3 Sum[C+]

@LeetCode三数の和--3 Sum[C+]

問題説明

解決方法及び複雑度分析

プログラム実装

問題の説明
n個の整数を含む配列numsを与え、numsにa,b,cの3つの要素が存在するか否かを判断し、a+b+c=0 a+b+c=0 a+b+c=0 a+b+c=0とする.条件を満たし、繰り返さないすべての三元グループを見つけます.
注意:答えに重複する三元グループは含まれてはいけません.
例えば、所与の配列nums=[-1,0,1,2,-1,-4]である.要求を満たす三元群の集合は,[−1,0,1][−1,−1,2]である.
解決方法及び複雑度分析
このような問題は2数の和から4数の和まで、その後私は4数の和をどのように解決するかを共有して、3数の和の方法と大同小異です.
配列内の3つの要素をそれぞれ指す3つのポインタを導入した.配列のループを容易にするために,ループを繰り返すことを避けるために,まず入力配列をソートする.次に、前の2つのポインタは前から後ろに遍歴し、残りのポインタは後から前に遍歴し、3つの数の和がゼロより大きい場合は、3番目のポインタを前に移動します.そうでない場合は、2番目のポインタを後ろに移動します.
三元グループが重複しないことを保証するために、ポインタが指す次の要素が現在のポインタ要素と同じ場合、ポインタは次の要素に移動します.
プログラム実装

	class Solution {
	public:
		vector<vector<int>> threeSum(vector<int>& nums) {
			vector<vector<int>> res;
			if(nums.empty()) return {};
			sort(nums.begin(), nums.end());
			for(int k = 0; k < nums.size(); k++) {
				if(k > 0 && nums[k] == nums[k - 1]) continue;
				int i = k + 1, j = nums.size() - 1;
				while(i < j) {
					if(nums[i] + nums[j] == -nums[k]) {
						res.push_back({nums[k], nums[i], nums[j]});
						while(i < j && nums[i] == nums[i + 1]) i++;
						while(i < j && nums[j - 1] == nums[j]) j--;
						i++; j--;
					} else if(nums[i] + nums[j] < -nums[k]) i++;
					else j--;
				}
			}
			return res;
		}
	};

@北京・懐柔2019.3.2