Problem
Given an array nums
of n integers and an integer target
, find three integers in nums
such that the sum is closest to target
. Return the sum of the three integers. You may assume that each input would have exactly one solution.
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).
Solution: Sorting + Two Pointers
Similar to 花花酱 LeetCode 15. 3Sum
Time complexity: O(n^2)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
// Author: Huahua, 8 ms class Solution { public: int threeSumClosest(vector<int> &num, int target) { int n = num.size(); int d = INT_MAX; int ans = target; sort(num.begin(), num.end()); for (int i = 0; i < n - 2; i++) { int s = i + 1, t = n - 1; while (s < t) { int sum = num[i] + num[s] + num[t]; if (sum == target) return target; int diff = abs(sum - target); if (diff < d) { d = diff; ans = sum; } if (sum > target) --t; else ++s; } } return ans; } }; |
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
// Author: Huahua class Solution { public int threeSumClosest(int[] nums, int target) { Arrays.sort(nums); int n = nums.length; int ans = 0; int d = Integer.MAX_VALUE; for (int i = 0; i < n - 2; ++i) { int s = i + 1; int t = n - 1; while (s < t) { int sum = nums[i] + nums[s] + nums[t]; if (sum == target) return target; int diff = Math.abs(sum - target); if (diff < d) { d = diff; ans = sum; } if (sum > target) --t; else ++s; } } return ans; } } |
Python3
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
# Author: Huahua class Solution: def threeSumClosest(self, nums, target): nums.sort() n = len(nums) d = 2**32 ans = 0 for i in range(n - 2): s, t = i + 1, n - 1 while s < t: sum3 = nums[i] + nums[s] + nums[t] if sum3 == target: return target diff = abs(sum3 - target) if diff < d: ans, d = sum3, diff if sum3 > target: t -= 1 else: s += 1 return ans |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment