首页 > 代码库 > [LeetCode] 3Sum 找出所有三个元素之和为0的组合

[LeetCode] 3Sum 找出所有三个元素之和为0的组合

本题是查找两个数使和为给定值的变形。

一开始采用的是维护两个下标(即目标三元组中的最小值和最大值),两边向中间逼近。针对两个下标,利用二分法找出介于二者之间的数。写完之后,有个数据过不去,原因在于两个下标有可能需要往外移动,而非仅仅是逼近,如:

[-4,-2,-2,-2,0,1,2,2,2,3,3,4,4,6,6]

三元组(-2,1,3)的下一个是(-2,-2,4),此时下标由3回复到4,而非往下移。

原因:x+y+z=0, x↑, z可能增或减。


正确做法:

只是在经典问题上做改进。枚举最小值num[i],然后在右边的元素中找出两个数使之和等于-num[i]即可。

去重可以通过三个下标单方向移的过程中,如果当前数与上一个数相同,则表明会出现重复值,因为此时其他两个数都不变,故需要跳过。


class Solution {
public:
	vector<vector<int> > threeSum(vector<int> &num) {
		int i=0,n=num.size(),j=n-1,status,k,sum;
		if(j<0)return vector<vector<int> >();
		sort(num.begin(),num.end());
		vector<vector<int> >ans;
		for(k=0;k<n-2;++k){
			if(k>0&&num[k]==num[k-1])continue;
			sum=-num[k];
			i=k+1,j=n-1;
			while(i<j){
				if(sum>num[i]+num[j]){
					++i; while(i<j&&i>=k+2&&num[i]==num[i-1])++i;
				}
				else if(sum<num[i]+num[j]){
					--j; while(i<j&&j<n-1&&num[j]==num[j+1])--j;
				}
				else{
					vector<int>vt;
					vt.push_back(num[k]);
					vt.push_back(num[i]);
					vt.push_back(num[j]);
					ans.push_back(vt);
					++i; while(i<j&&i>=k+2&&num[i]==num[i-1])++i;
				}
			}
		}
		return ans;
    }
};


[LeetCode] 3Sum 找出所有三个元素之和为0的组合