The Solution to LeetCode 15 3Sum

Question:

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

这里的Note我在一开始想算法的时候没注意到，好像结果里边出现了重复的三个数，先贴上我的代码，不管啦！！这个改进问题留在下篇好了，警示自己先把题目读完，没读完就造成这种后果啦。

再说说思路吧，看到给出的例子，我就按照例子来想方法，思考过程的图片如下……

Answer:

class Solution { public: vector<vector<int> >* r; vector<vector<int>> threeSum(vector<int>& nums) { r= new vector<vector<int>>(); if(nums.size()<3) { return *r; } sort(nums.begin(), nums.end()); int i=0; int j=1; int p=2; for (i=0,j=1;j<nums.size()-1;i++,j++) { for(p=2;p<nums.size();p++) { if(nums[i]+nums[j]+nums[p]==0) { vector<int> tmp; tmp.push_back(nums[i]); tmp.push_back(nums[j]); tmp.push_back(nums[p]); r->push_back(tmp); } } } return *r; } };

Run Code Result:

Your input

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

Your answer

[[-1,-1,2],[-1,0,1],[0,1,-1]]

Expected answer

[[-1,-1,2],[-1,0,1]]