[LeetCode]3-SUM改良

class Solution {
public:
	vector<vector<int> > threeSum(vector<int> &num) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function

		vector<vector<int> > ret;
		ret.clear();
		sort(num.begin(), num.end());
		for(int i=0; i!=num.size(); i++)
		{
			//avg = 269.2 ms
			if (num[i]>0)
			//avg = 253.2 ms
				break;
			if (i > 0 && num[i]==num[i-1])
				continue;
				
			int j,k;
			j = i+1;
			k = num.size()-1;
			while (j<k) {
				if (j>i+1 && num[j]==num[j-1]) { 
					j++;					
					continue;
				}
				if (k<num.size()-1 && num[k]==num[k+1]) {
					k--;
					continue;
				}
				int sum = num[i] + num[j] + num[k];
				if (sum>0) {
					k--;
				}else if (sum<0) {
					j++;
				}else {
					vector<int> tmp;
					tmp.push_back(num[i]);
					tmp.push_back(num[j]);
					tmp.push_back(num[k]);
					ret.push_back(tmp);
					j++;
				}
			}
		}
	return ret;
	}
};

比較判断文を入れる

if (num[i]>0)
    break;

以前、LeetCodeは時間統計を通過しました:

// no compare  time:ms
276
276
284
256
268

272
244
268
268
280

avg1 = 269.2 ms

比較判定文を加えた後のLeetCode通過時間統計:

// if(num[i]>0)	break;
260
248
272
280
248

248
244
244
244
244

avg2 = 253.2 ms

avg 1=269.2 ms,avg 2=253.2 msでは,通過時間が著しく低下した.