LeetCode刷题（C++）——3Sum Closest（Medium）

深碍√TFBOYSˉ_ 2022-06-16 04:07 183阅读 0赞

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)

**思路：此题类似于3Sum这道题，在3Sum那道题的基础上稍微修改一下即可http://blog.csdn.net/yf\_li123/article/details/71176581**

class Solution {
    public:
        int threeSumClosest(vector<int>& nums, int target) {
            sort(nums.begin(), nums.end());
    		int closest = INT_MAX;
    		int ans = 0;
    		for (int start = 0; start < nums.size();start++)
    		{
    			int i = start + 1;
    			int j = nums.size() - 1;
    			while (i < j)
    			{
    				int sum = nums[i] + nums[j] + nums[start];
    				if (sum == target)
    					return target;
    				else if (sum < target)
    				{
    					if ((target - sum) < closest)
    					{
    						closest = target - sum;
    						ans = sum;
    					}
    					while (i + 1 < nums.size() && nums[i] == nums[i + 1])
    						i++;
    					i++;
    				}
    				else
    				{
    					if ((sum - target) < closest)
    					{
    						closest = sum - target;
    						ans = sum;
    					}
    					while (j - 1 >= 0 && nums[j] == nums[j - 1])
    						j--;
    					j--;
    				}
    			}
    			while (start + 1 < nums.size() && nums[start] == nums[start + 1])
    				start++;
    		}
    		return ans;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，183人围观）

还没有评论，来说两句吧...

相关阅读

相关 leetcode刷题（3）

各位朋友们大家好，今天是我leedcode刷题系列的第三篇，废话不多说，直接进入主题。文章目录分割链表题目要求用例输入

古城微笑少年丶/ 2023年09月25日 23:08/ 0 赞/ 56 阅读

相关 LeetCode刷题（C++）——4Sum（Medium）

Given an array S of n integers, are there elements a, b, c, and d in S such that a \+ b

素颜马尾好姑娘i/ 2022年06月16日 07:11/ 0 赞/ 186 阅读

相关 LeetCode刷题（C++）——Minimum Path Sum（Medium）

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom

分手后的思念是犯贱/ 2022年06月16日 06:29/ 0 赞/ 172 阅读

相关 LeetCode刷题（C++）——3Sum Closest（Medium）

Given an array S of n integers, find three integers in S such that the sum is closest to

深碍√TFBOYSˉ_/ 2022年06月16日 04:07/ 0 赞/ 184 阅读

相关 LeetCode刷题（C++）——3Sum（Medium）

Given an array S of n integers, are there elements a, b, c in S such that a \+ b \+ c =

骑猪看日落/ 2022年06月16日 04:06/ 0 赞/ 158 阅读

相关 LeetCode刷题（C++）——Path Sum II（Medium）

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals

╰半夏微凉°/ 2022年06月16日 00:21/ 0 赞/ 156 阅读

相关 LeetCode刷题（C++）——Path Sum（Easy）

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that a

蔚落/ 2022年06月16日 00:21/ 0 赞/ 150 阅读

相关【LeetCode.15】3Sum （C++）

问题描述 > Given an array nums of n integers, are there elements a, b, c in nums such tha

阳光穿透心脏的1/2处/ 2022年04月25日 03:10/ 0 赞/ 175 阅读

相关 LeetCode刷题——Day3

6、将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。比如输入字符串为 `"LEETCODEISHIRING"` 行数为 3 时，排列如下：

快来打我*/ 2022年03月27日 01:19/ 0 赞/ 268 阅读

相关 Leetcode c语言-3Sum Closest

Title: Given an array S of n integers, find three integers in S such that the sum is...

小灰灰/ 2021年03月28日 14:17/ 0 赞/ 426 阅读