[LeetCode] 16. 3Sum Closest

轉自LeetCode

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

    For example, given array S = {-1 2 1 -4}, and target = 1.

    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

<Solution>

這題是 3sum 的衍生題

基本想法都還是一樣，只是一些檢查條件不一樣

先排序，固定一個數，然後再去歷遍剩下兩個數的組合

這次不去記錄數組，而是和 target 的差距絕對值最小值

那因為題目有說只會有一組解，所以在一開始固定第一個數的時候

如果有重複，也不用再檢查了

code 如下

C++

	class Solution {
	public:
	int threeSumClosest(vector<int>& nums, int target) {
	int ans = INT_MAX;
	int diff = INT_MAX;
	//>> sort first
	sort(nums.begin(), nums.end());
	const int len = nums.size();
	const int total = len - 2;
	int sum, newDiff;
	int left, right;
	for(int i = 0; i < total; i++) {
	if(i == 0 || (nums[i] <= target && nums[i] != nums[i-1])) {
	left = i+1;
	right = len - 1;
	while(left < right) {
	sum = nums[i] + nums[left] + nums[right];
	newDiff = abs(target - sum);
	if(diff > newDiff) {
	diff = newDiff;
	ans = sum;
	}
	if(sum < target) {
	++left;
	}
	else {
	--right;
	}
	}
	}
	}
	return ans;
	}
	};

view raw threeSumCloest.cpp hosted with ❤ by GitHub

Java

	public class Solution {
	public int threeSumClosest(int[] nums, int target) {
	int ans = 0;
	int diff = Integer.MAX_VALUE;
	//>> sort first
	Arrays.sort(nums);
	int sum, newDiff;
	int left, right;
	final int len = nums.length;
	final int total = len - 2;
	for(int i = 0; i < total; i++) {
	if(i == 0 || (nums[i] <= target && nums[i] != nums[i-1])) {
	left = i + 1;
	right = len - 1;
	while(left < right) {
	sum = nums[i] + nums[left] + nums[right];
	newDiff = Math.abs(target - sum);
	if(diff > newDiff) {
	diff = newDiff;
	ans = sum;
	}
	if(sum < target) {
	++left;
	}
	else {
	--right;
	}
	}
	}
	}
	return ans;
	}
	}

view raw threeSumCloest.java hosted with ❤ by GitHub

kotlin

	class Solution {
	fun threeSumClosest(nums: IntArray, target: Int): Int {
	var ans = Int.MAX_VALUE
	var left: Int
	var right: Int
	var diff = Int.MAX_VALUE
	var newDiff: Int
	var sum: Int
	nums.sort()
	for (i in nums.indices) {
	left = i + 1
	right = nums.size - 1
	while (left < right) {
	sum = nums[i] + nums[left] + nums[right]
	newDiff = Math.abs(target - sum)
	if (newDiff < diff) {
	ans = sum
	diff = newDiff
	}
	if (sum < target) {
	++left
	} else {
	--right
	}
	}
	}
	return ans
	}
	}

view raw 3Sum_closest.kt hosted with ❤ by GitHub