给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组。

注意:答案中不可以包含重复的三元组。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/3sum
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

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

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

# @param {Integer[]} nums
# @return {Integer[][]}
def three_sum(nums)
    return [] if nums.length < 3
    t = []
    h = {}
    nums.sort!
        
    i = 0
    l = i + 1
    r = nums.length - 1
    while nums[i] && nums[i] <= 0
       
        if l >= r || (i > 0 && nums[i] == nums[i-1])
            i += 1 
            l = i+1
            r = nums.length - 1
            next
        end    
        
        res = nums[i] + nums[l] + nums[r]
        if res == 0 && h["#{nums[i]}_#{nums[l]}_#{nums[r]}"].nil?
            t.push([nums[i], nums[l], nums[r]]) 
            h["#{nums[i]}_#{nums[l]}_#{nums[r]}"] = 1
        end    
        if res <= 0
            l += 1
        else
            r -= 1
        end    
    end    
    
    t
end
  • 首先对数组进行排序,排序后固定一个数 nums[i]nums[i],再使用左右指针指向 nums[i]nums[i]后面的两端,数字分别为 nums[L]nums[L] 和 nums[R]nums[R],计算三个数的和 sumsum 判断是否满足为 00,满足则添加进结果集
  • 如果 nums[i]nums[i]大于 00,则三数之和必然无法等于 00,结束循环
  • 如果 nums[i]nums[i] == nums[i-1]nums[i−1],则说明该数字重复,会导致结果重复,所以应该跳过
  • 当 sumsum == 00 时,nums[L]nums[L] == nums[L+1]nums[L+1] 则会导致结果重复,应该跳过,LL
  • 当 sumsum == 00 时,nums[R]nums[R] == nums[R-1]nums[R−1] 则会导致结果重复,应该跳过,R–R−−