3-sum-closest

问题

[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]
]

解析

和3-sum问题不一样的是，这次要寻找的不是三个数只和为0，而是最接近target的三个元素之和。

但是思路还是共通的。我们首先对nums进行排序，然后遍历排序好的数组sorted。

对于每个数组的元素sorted[i], 我们初始化左边界left为i+1，右边界为right-1。然后根据 sorted[i] + sorted[left] + sorted[right]和target的比较结果去移动边界。

我们初始化最小差距 min= sorted[0] + sorted[1] + sorted[2] - target

每当sorted[i] + sorted[left] + sorted[right] - target的绝对值小于min的绝对值，我们更新min。

每当sorted[i] + sorted[left] + sorted[right] - target > 0 说明三个数只和太大了，我们移动右边界减少三个数之和。

每当sorted[i] + sorted[left] + sorted[right] - target < 0 说明三个数只和太小了，我们移动左边界增加三个数之和。

当sorted[i] + sorted[left] + sorted[right] - target == 0 那最好，我们直接返回target。

当遍历完最后一个元素，我们返回min + target

解法

# @param {Integer[]} nums
# @param {Integer} target
# @return {Integer}
def three_sum_closest(nums, target)
  sorted = nums.sort
  i = 0
  min = sorted[0] + sorted[1] + sorted[2] - target
  while i < sorted.length - 2
    if i > 0 && sorted[i] == sorted[i-1]
      i+=1
      next
    end
    left = i+1
    right = sorted.length - 1
    while (left < right)
      if (sorted[left] + sorted[right] + sorted[i] - target).abs < min.abs
        min = sorted[left] + sorted[right] + sorted[i] - target
      end
      if sorted[left] + sorted[right] + sorted[i] - target > 0
        right -=1
      elsif sorted[left] + sorted[right] + sorted[i] - target < 0
        left +=1
      else
        return sorted[left] + sorted[right] + sorted[i]
      end
      if left + 1 < right && sorted[left] == sorted[left+1]
        left+=1
        next
      end
      if right - 1 > left && sorted[right] == sorted[right-1]
        right-=1
        next
      end
    end
    i += 1
  end
  return min + target
end

puts three_sum_closest([-1,0,1,1,55], 3)

反思

还好这题在每看结果的情况下通过了。为了二刷还是mark一下吧。