3-sum

题目

[15] 3Sum  

https://leetcode.com/problems/3sum/description/

* algorithms
* Medium (24.60%)
* Total Accepted:    631K
* Total Submissions: 2.6M
* Testcase Example:  '[-1,0,1,2,-1,-4]'

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.

Note:

The solution set must not contain duplicate triplets.

Example:


Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

思考

乍看题目的时候第一反应是先sort，说明已经步入正轨了。

然而自己最初的尝试是去固定两个数，寻找第三个数。然后根据第三个数去移动两边，结果没能很好处理边界问题。

正确解法的答案是固定一个数，然后去寻找另外两个数，遇到相同数字时候的处理方法，相对就比较直观简单了。

解法

首先进行sort。sort的时间复杂度是O(nlogn). 远远在暴力解法至少两层循环的log(n^3)之下。

sort之后，我们进行循环。对于每个元素sorted[i], 我们使用两边夹逼去寻找符合条件的sorted[left], sorted[right]。

注意跳过重复的元素。

def three_sum(nums)
  sorted = nums.sort
  i = 0
  j = sorted.length - 1
  result = []
  for i in 0..sorted.length - 3
    next if (i > 0 && sorted[i] == sorted[i-1])
    target = 0 - sorted[i]
    left = i+1
    right = sorted.length - 1
    while (left < right)
      a = sorted[left]
      b = sorted[right]
      if (a + b == target)
        result << [a,b, sorted[i]].sort
        while(sorted[left+1] == a && left < right)
          left+=1
        end
        while(sorted[right-1] == b && left < right)
          right -=1
        end
        left+=1
        right-=1
      elsif a+b < target
        left +=1
      else 
        right -=1
      end
    end
  end
  return result
end