15. 3Sum

1. 问题描述

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.

For example, given array S = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
    [-1, 0, 1],
    [-1, -1, 2]
]

Tags： Array Two Pointers

Similar Problems： (E) Two Sum (M) 3Sum Closest (M) 4Sum (M) 3Sum Smaller

2. 解答思路

3. 代码

  1 #include <vector>
  2 #include <map>
  3 #include <algorithm>
  4 using namespace std;
  5 class Solution {
  6 public:
  7     vector<vector<int>> threeSum(vector<int>& nums) {
  8         vector<vector<int>> ResultVec;
  9         bool bIsValidate = Validate(nums);
 10         if (!bIsValidate)
 11         {
 12             return ResultVec;
 13         }
 14         int idx = 0;
 15         int Fir = 0;
 16         int Sec = nums.size() - 1;
 17 
 18         while (nums[idx] <= 0)
 19         {
 20             int target = -nums[idx];
 21             Fir = idx + 1;
 22             Sec = nums.size() - 1;
 23             int sum;
 24             while (Fir < Sec)
 25             {
 26                 sum = nums[Fir] + nums[Sec];
 27                 if (sum > target)
 28                 {
 29                     Sec--;
 30                 }
 31                 else if (sum < target)
 32                 {
 33                     Fir++;
 34                 }
 35                 else
 36                 {
 37                     std::vector<int> tVec;
 38                     tVec.push_back(nums[idx]);
 39                     tVec.push_back(nums[Fir]);
 40                     tVec.push_back(nums[Sec]);
 41                     ResultVec.push_back(tVec);
 42 
 43                     int t = nums[Fir];
 44                     Fir++;
 45                     while (Fir != Sec)
 46                     {
 47                         if (t != nums[Fir])
 48                         {
 49                             break;
 50                         }
 51                         Fir++;
 52                     }
 53                 }
 54             }
 55             int t = nums[idx];
 56             idx++;
 57             while (nums[idx] <= 0)
 58             {
 59                 if (t != nums[idx])
 60                 {
 61                     break;
 62                 }
 63                 idx++;
 64             }
 65         }
 66         return ResultVec;
 67     }
 68 private:
 69     bool Validate(vector<int>& nums)
 70     {
 71         //判断数组的Size是否满足要求，非空且Size至少>3
 72         int vSize = nums.size();
 73         if (vSize < 3)
 74         {
 75             return false;
 76         }
 77 
 78         std::sort(nums.begin(), nums.end());
 79         //边界检查
 80         if (nums[0] > 0 || nums[vSize-1] < 0)//若数组中全是负数或者全是非的整数
 81         {
 82             return false;
 83         }
 84 
 85         int t = nums[vSize-1];
 86         int n = 0;//用于记录与nums[vSize-1]值相同的数字的个数
 87         for (int i=1; vSize-i>=0; i++)
 88         {
 89             if (t == nums[vSize-i])
 90             {
 91                 n++;
 92             }
 93             else
 94             {
 95                 break;
 96             }
 97         }
 98         if (nums[vSize-1] == 0 && n<3)//如[-3, -2, -1, 0, 0]
 99         {
100             return false;
101         }
102         return true;
103     }
104 };

4. 反思

第一遍做的时候忘记了进行边界检查！！！