LeetCode_16: 3Sum Closest

# 引言

题目链接：https://leetcode.com/problems/3sum-closest/description/

# 题目大意

给出一个包含n个整数的数组nums和一个目标数字target, 在数组中找到三个整数使得它们的总和最接近目标target, 输出这个最接近目标值的数字

• Example

Given array nums = [-1, 2, 1, -4], and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

# 题解

这题其实是第15题的变种, 相信看了这篇题解举一反三很容易能拿下这题, LeetCode:15.3Sum题解, Click Here!

第15题是找到所有三个数的和等于0的组合, 这题是找到三个数的和接近目标值, 其实除了返回的结果不同整个过程都是类似的, 只需要在15题的判断条件上进行修改即可, 判断条件修改如下

由于数组有序, 根据当前选取三个数字的和和目标值比较, 大于目标值, 第三个数字从剩余数组从后往前选取, 小于目标值, 第二个数字从剩余数组从前往后选取, 每次选定三个目标后将选取数字的和和目标值差值比较, 更新更小差值的数组和即可

int curSum = nums[i] + nums[midIndex] + nums[lastIndex];
if (curSum == target) return target;
else if (curSum > target) --lastIndex;
else ++midIndex;
retAns = abs(retAns - target) < abs(curSum - target) ? retAns : curSum;

# 复杂度

时间复杂度 O(n^2)

空间复杂度 O(1)

# AC代码

c++版本

class Solution
{
  public:
    int threeSumClosest(vector<int> &nums, int target)
    {
        int retAns = 0x3f3f3f3f;
        const int len = nums.size();
        std::sort(nums.begin(), nums.end());
        for (int i = 0; i < len - 2; ++i)
        {
            if (i > 0 && nums[i] == nums[i - 1])
            {
                continue;
            }
            int midIndex = i + 1;
            int lastIndex = len - 1;
            while (midIndex < lastIndex)
            {
                int curSum = nums[i] + nums[midIndex] + nums[lastIndex];
                if (curSum == target)
                {
                    return target;
                }
                else if (curSum > target)
                {
                    --lastIndex;
                    while (midIndex < lastIndex && nums[lastIndex + 1] == nums[lastIndex])
                    {
                        --lastIndex;
                    }
                }
                else
                {
                    ++midIndex;
                    while (midIndex < lastIndex && nums[midIndex - 1] == nums[midIndex])
                    {
                        ++midIndex;
                    }
                }
                retAns = abs(retAns - target) < abs(curSum - target) ? retAns : curSum;
            }
        }
        return retAns;
    }
};

go版本

func intAbs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

func threeSumClosest(nums []int, target int) int {
	retAns, lens := 0x3f3f3f3f, len(nums)
	sort.Sort(sort.IntSlice(nums))
	for i := 0; i < lens-2; i++ {

		if i > 0 && nums[i] == nums[i-1] {
			continue
		}
		midIndex, lastIndex := i+1, lens-1
		for midIndex < lastIndex {
			curSum := nums[i] + nums[midIndex] + nums[lastIndex]
			if curSum == target {
				return target
			} else if curSum > target {
				lastIndex--
				for midIndex < lastIndex && nums[lastIndex+1] == nums[lastIndex] {
					lastIndex--
				}
			} else {
				midIndex++
				for midIndex < lastIndex && nums[midIndex-1] == nums[midIndex] {
					midIndex++
				}
			}
			if intAbs(curSum-target) < intAbs(retAns-target) {
				retAns = curSum
			}
		}
	}
	return retAns
}