3 Sum

发布于 2025-02-22 13:01:23 字数 3897 浏览 0 评论 0 收藏 0

Source

leetcode: 3Sum | LeetCode OJ
lintcode: (57) 3 Sum

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.

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

(-1, 0, 1)
(-1, -1, 2)
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.

题解 1 - 排序 + 哈希表 + 2 Sum

相比之前的 2 Sum , 3 Sum 又多加了一个数，按照之前 2 Sum 的分解为『1 Sum + 1 Sum』的思路，我们同样可以将 3 Sum 分解为『1 Sum + 2 Sum』的问题，具体就是首先对原数组排序，排序后选出第一个元素，随后在剩下的元素中使用 2 Sum 的解法。

Python

class Solution:
  """
  @param numbersbers : Give an array numbersbers of n integer
  @return : Find all unique triplets in the array which gives the sum of zero.
  """
  def threeSum(self, numbers):
    triplets = []
    length = len(numbers)
    if length < 3:
      return triplets

    numbers.sort()
    for i in xrange(length):
      target = 0 - numbers[i]
      # 2 Sum
      hashmap = {}
      for j in xrange(i + 1, length):
        item_j = numbers[j]
        if (target - item_j) in hashmap:
          triplet = [numbers[i], target - item_j, item_j]
          if triplet not in triplets:
            triplets.append(triplet)
        else:
          hashmap[item_j] = j

    return triplets

源码分析

异常处理，对长度小于 3 的直接返回。
排序输入数组，有助于提高效率和返回有序列表。
循环遍历排序后数组，先取出一个元素，随后求得 2 Sum 中需要的目标数。
由于本题中最后返回结果不能重复，在加入到最终返回值之前查重。

由于排序后的元素已经按照大小顺序排列，且在 2 Sum 中先遍历的元素较小，所以无需对列表内元素再排序。

复杂度分析

排序时间复杂度 O(nlogn)O(n \log n)O(nlogn), 两重 for 循环，时间复杂度近似为 O(n2)O(n^2)O(n2)，使用哈希表（字典) 实现，空间复杂度为 O(n)O(n)O(n).

目前这段源码为比较简易的实现，leetcode 上的运行时间为 500 + ms, 还有较大的优化空间，嗯，后续再进行优化。

C++

class Solution {
public:
  vector<vector<int> > threeSum(vector<int> &num) 
  {
    vector<vector<int> > result;
    if (num.size() < 3) return result;

    int ans = 0;

    sort(num.begin(), num.end());

    for (int i = 0;i < num.size() - 2; ++i)
    {
      if (i > 0 && num[i] == num[i - 1])  
        continue;
      int j = i + 1;
      int k = num.size() - 1;

      while (j < k)
      {
        ans = num[i] + num[j] + num[k];

        if (ans == 0)
        {
          result.push_back({num[i], num[j], num[k]});
          ++j;
          while (j < num.size() && num[j] == num[j - 1])
            ++j;
          --k;
          while (k >= 0 && num[k] == num[k + 1])
            --k;
        }
        else if (ans > 0) 
          --k;
        else 
          ++j;
      }
    }

    return result;
  }
};

源码分析

同 python 解法不同，没有使用 hash map

S = {-1 0 1 2 -1 -4}
排序后：
S = {-4 -1 -1 0 1 2}
    ↑  ↑    ↑
    i  j    k
     →    ←
i 每轮只走一步，j 和 k 根据 S[i]+S[j]+S[k]=ans 和 0 的关系进行移动，且 j 只向后走（即 S[j]只增大），k 只向前走（即 S[k]只减小）
如果 ans>0 说明 S[k]过大，k 向前移；如果 ans<0 说明 S[j]过小，j 向后移；ans==0 即为所求。
至于如何取到所有解，看代码即可理解，不再赘述。