3Sum

  • 首先排序
  • 双指针，当我们需要枚举数组中的两个元素时，如果我们发现随着第一个元素的递增，第二个元素是递减的，那么就可以使用双指针的方法
    1. Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
    2. Note:
    3. The solution set must not contain duplicate triplets.
    4. Example:
    5. Given array nums = [-1, 0, 1, 2, -1, -4],
    6. A solution set is:
    7. [
    8. [-1, 0, 1],
    9. [-1, -1, 2]
    10. ]
    11. //--------------------------------------------
    12. class Solution {
    13. public:
    14.   vector<vector<int>> threeSum(vector<int>& nums) {
    15.       int n = nums.size();
    16.       sort(nums.begin(), nums.end());
    17.       vector<vector<int> > ans; 
    18.       for (int first = 0; first < n; first++) {
    19.           if (first > 0 && nums[first] == nums[first - 1]) {
    20.               continue;
    21.           }
    22.           int third = n-1;
    23.           for (int second = first + 1; second < n; second++) {
    24.               if (second > first + 1 && nums[second] == nums[second-1]) {
    25.                   continue;
    26.               }
    27.               while(second < third && nums[first] + nums[second] + nums[third] > 0) {
    28.                   third--;
    29.               }
    30.               if (second == third) {
    31.                   break;
    32.               }
    33.               if (nums[first] + nums[second] + nums[third] == 0) {
    34.                   ans.push_back({nums[first], nums[second], nums[third]});
    35.               }
    36.           }
    37.       }
    38.       return ans;
    39.   }
    40. };