【LeetCode】LeetCode——第15題：3Sum

15. 3Sum

Given an arraySofnintegers, are there elementsa,b,cinSsuch thata+b+c= 0? Find all unique triplets in the array which gives the sum of zero.

Note:

• Elements in a triplet (a,b,c) must be in non-descending order. (ie,a≤b≤c)
• The solution set must not contain duplicate triplets.

      For example, given array S = {-1 0 1 2 -1 -4},    A solution set is:    (-1, 0, 1)    (-1, -1, 2)

  Subscribeto see which companies asked this question

  Show Tags Show Similar Problems            
  

  題目的大概意思是：給定一組整數，找出所有能使和為0的三個數，且不重復。

  這道題難度等級：中等

  思路：

  1、與題目Two Sum類似，先將數組nums進行排序，然後從左往右依次枚舉，在枚舉的過程中左右夾逼；

  2、枚舉位置為i，當nums[i]為正數時，結束枚舉（因為不可能三個正數之和為0）；另外，要枚舉過整數不再重復枚舉；

  3、枚舉到i時，左、右位置分別用l、r表示，當nums[i]+nums[l]+nums[r]>0，右邊界往左夾逼；當nums[i]+nums[l]+nums[r]<0，左邊界往右夾逼；當nums[i]+nums[l]+nums[r]==0，則算找到一個，要存起來，再將左邊界往右夾逼同時要跳過與之前左邊界相同的值，否則會出現重復的三個數。

  4、在步驟3的整個過程中，始終要保證l。

  代碼如下：

  class Solution {public:    vector> threeSum(vector& nums) {		vector > res;		sort(nums.begin(), nums.end());		vector tmp(3,0);		int l, r;		for (int i = 0; i < nums.size() && nums[i] <= 0; ++i){//從左往右枚舉			if (nums[i] != nums[i - 1] || i == 0){				l = i + 1; r = nums.size() - 1;				while(l < r ){					while (l < r && nums[i] + nums[l] + nums[r] > 0){--r;}//限制右邊界					if (l < r && nums[i] + nums[l] + nums[r] == 0){					    tmp[0] = nums[i]; tmp[1] = nums[l]; tmp[2] = nums[r];					    res.push_back(tmp);						while(l < r && nums[l] == tmp[1]){++l;}//限制左邊界					}					else{						++l;					}				}			}		}		return res;    }};

  提交代碼後，AC掉該題，Runtime:52 ms。