LeetCodeDay35 —— 三数之和★★☆

15. 三数之和

描述

• 给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
• 注意：答案中不可以包含重复的三元组。

示例

  给定数组 nums = [-1, 0, 1, 2, -1, -4]，

  满足要求的三元组集合为：
  [
    [-1, 0, 1],
    [-1, -1, 2]
  ]

思路

1. 暴力解法，O(n^3)的复杂度，注意利用do while 去除重复的元素。
2. 两指针求和，将题目从求三数之和等于 0. 转换为求 a + b = -c, 即求数组中两数之和等于目标数。此处可以将数组排序，然后两指针一头一尾求解。(参考)

Tips

• 化繁为简，将复杂的问题转换为熟悉的小问题。
• 写出暴力解法，然后通过转换降低复杂度。将大的问题分解为小的。如本题，确定一个数后，要求另外两数之和等于 -c，这样如果能将这部分的复杂度降下来，就能将整体的复杂度降低下来了。
• 实现的时候要注意删减枝叶，如本题利用do while / continue 来解决去重的问题，比全部加进去后再判断就要好的多。

class Solution_15_01 {
 public:
  vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> ret;
    sort(nums.begin(), nums.end());
    int size = nums.size();
    for (int i = 0; i < size;) {
      for (int j = i + 1; j < size;) {
        for (int k = j + 1; k < size;) {
          if (nums[i] + nums[j] + nums[k] == 0) {
            vector<int> tmp;
            tmp.push_back({nums[i], nums[j], nums[k]});
            ret.push_back(tmp);
          }
          do {
            ++k;
          } while (k < size && nums[k - 1] == nums[k]);
        }
        do {
          ++j;
        } while (j < size && nums[j - 1] == nums[j]);
      }
      do {
        ++i;
      } while (i < size && nums[i - 1] == nums[i]);
    }
    return ret;
  }
};

class Solution_15_02 {
 public:
  vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> ret;
    sort(nums.begin(), nums.end());
    int size = nums.size();
    for (int i = 0; i < size - 2;) {
      if (nums[i] > 0) break;  // 此处不能 >= 要考虑 0.0.0 的情况
      int target = 0 - nums[i];
      int j = i + 1;
      int k = size - 1;
      while (j < k) {
        if (nums[j] + nums[k] < target) {
          ++j;
        } else if (nums[j] + nums[k] > target) {
          --k;
        } else {
          vector<int> tmp;
          tmp.push_back({nums[i], nums[j], nums[k]});
          ret.push_back(tmp);
          do {
            ++j;
          } while (j < k & nums[j - 1] == nums[j]);
          do {
            --k;
          } while (j < k & nums[k + 1] == nums[k]);
        }
      }
      do {
        ++i;
      } while (i < size & nums[i - 1] == nums[i]);
    }
    return ret;
  }
};

// 与解法2的思路一致，只是实现不同，附在此处供参考
class Solution_15_03 {
 public:
  vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> rs;
    if (nums.size() == 0) return rs;

    sort(nums.begin(), nums.end());
    for (int i = 0; i < nums.size() - 2; i++) {
      if (nums[i] > 0) return rs;
      if (i != 0 && nums[i] == nums[i - 1]) continue;
      int tmpTarget = 0 - nums[i];

      int beg = i + 1, end = nums.size() - 1;
      while (beg < end) {
        if (nums[beg] + nums[end] == tmpTarget) {
          rs.push_back({nums[i], nums[beg], nums[end]});
          while (beg < end - 1 && nums[end] == nums[end - 1]) end--;
          end--;
        } else if (nums[beg] + nums[end] > tmpTarget)
          end--;
        else
          beg++;
      }
    }
    return rs;
  }
};