8000 [LeetCode] 16. 3Sum Closest · Issue #16 · grandyang/leetcode · GitHub
[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to content
/ leetcode Public

[LeetCode] 16. 3Sum Closest #16

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Open
grandyang opened this issue May 30, 2019 · 3 comments
Open

[LeetCode] 16. 3Sum Closest #16

grandyang opened this issue May 30, 2019 · 3 comments

Comments

@grandyang
Copy link
Owner
grandyang commented May 30, 2019 •
edited
Loading


请点击下方图片观看讲解视频
Click below image to watch YouTube Video
Video

Given an integer array nums of length n 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 1:

**Input:** nums = [-1,2,1,-4], target = 1
**Output:** 2
**Explanation:** The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Example 2:

**Input:** nums = [0,0,0], target = 1
**Output:** 0
**Explanation:** The sum that is closest to the target is 0. (0 + 0 + 0 = 0). 

Constraints:

  • 3 <= nums.length <= 500
  • -1000 <= nums[i] <= 1000
  • -104 <= target <= 104

这道题让我们求最接近给定值的三数之和，是在之前那道 3Sum 的基础上又增加了些许难度，那么这道题让返回这个最接近于给定值的值，即要保证当前三数和跟给定值之间的差的绝对值最小，所以需要定义一个变量 diff 用来记录差的绝对值，然后还是要先将数组排个序，然后开始遍历数组，思路跟那道三数之和很相似，都是先确定一个数，然后用两个指针 left 和 right 来滑动寻找另外两个数，每确定两个数，求出此三数之和，然后算和给定值的差的绝对值存在 newDiff 中，然后和 diff 比较并更新 diff 和结果 closest 即可，代码如下：

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int closest = nums[0] + nums[1] + nums[2], n = nums.size();
        int diff = abs(closest - target);
        sort(nums.begin(), nums.end());
        for (int i = 0; i < n - 2; ++i) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int left = i + 1, right = n - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                int newDiff = abs(sum - target);
                if (diff > newDiff) {
                    diff = newDiff;
                    closest = sum;
                }
                if (sum < target) ++left;
                else --right;
            }
        }
        return closest;
    }
};

Github 同步地址：

#16

类似题目：

3Sum Smaller

3Sum

参考资料：

https://leetcode.com/problems/3sum-closest/

https://leetcode.com/problems/3sum-closest/discuss/7883/C%2B%2B-solution-O(n2)-using-sort

https://leetcode.com/problems/3sum-closest/discuss/7872/Java-solution-with-O(n2)-for-reference

LeetCode All in One 题目讲解汇总(持续更新中...)

（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，快快加入吧～）

知识星球 喜欢请点赞，疼爱请打赏❤️~.~

微信打赏

|

Venmo 打赏


---|---
@lld2006
Copy link
lld2006 commented Oct 20, 2019

可以优化一下， 当nums[i] *3 > target 的时候直接return nums[i]+nums[i+1]+nums[i+2] 和当前closest中最接近的那个

@grandyang
Copy link
Owner Author

已添加，多谢指出～

@zhaodonglin
Copy link

if (nums[i] * 3 > target) return min(closest, nums[i] + nums[i + 1] + nums[i + 2]);
should be like this:
if (nums[i] * 3 > target) {
total = nums[i] + nums[i + 1] + nums[i + 2];
if (abs(total-target) < diff) { return total;}
else{return closest}
}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
3 participants
@lld2006 @grandyang @zhaodonglin
0