题目描述 给定一个包括 n 个整数的数组 nums和 一个目标值 target。找出 nums中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。 例如，给定数组 nums = [-1，2，1，-4], 和 target = 1. 与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2). https://leetcode-cn.com/problems/3sum-closest/ 解法1 这道题目与三数之和非常相似, 不同之处在于本题要求解的是最接近目标值的三数之和而不要求三数之和为0. 另一个不同点是, 题目给定的输入能保证只存在唯一答案. 我们还是使用“三数之和”解法1的做法, 首先将数组nums排序,以降低内层循环的时间复杂度. 变量i依次访问数组nums的每个元素, 作为外层循环. 内层循环中, 我们用j, k指针分别指向i之后数组的两端. 我们将nums[i]+nums[j]+nums[k]与target之差的绝对值记为diff, diff的初值为Integer.MAX_VALUE. 如果nums[i]+nums[j]+nums[k]与target之差的绝对值小于diff, 则更新diff. 题目要求nums[i]+nums[j]+nums[k]的和, 那么我们除了记录diff之外, 还应该记录与diff对应的三个数之和, 我们计作threeSum. 现在我们分析下如何维护变量j与k. 如果三个数之和小于target, 那么说明我们要找更大的数才能使三数之和更接近target, 所以j自增1. 如果三数之和大于target, 说明我们从右边选的数太大了, 应该k自减1. 如果三数之和与target相等, 那么三数之和与target的差距是0, 这是最接近target的情况了. 注意, 如果遇到这种情况,…

题目描述 给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。 注意：答案中不可以包含重复的三元组。 例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]， 满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ] https://leetcode-cn.com/problems/3sum/ 解法1 首先对原数组nums进行排序, 用指针i指向nums的每个元素, 然后另指针j=i+1, k=|nums|-1. 指针j与k相向而行, 直到nums[i]+nums[j]+nums[k] == 0我们就找到了一个解, 此时需要继续相向而行直到k>=j. 将数组排序可以把算法的时间复杂度降低到O(n^2). 若不对数组排序, 为了寻找j, k使得nums[i]+nums[j]+nums[k] == 0, 需要使用双重循环遍历nums, 这样会使复杂度达到O(n^3). 因为题目要求“不可以包含重复的三元组”, 这就需要我们一旦找到符合条件的i, j, k. 就需要跳过nums中相同的元素(代码中被标记的部分), 以避免寻找重复的解. 例如…