LeetCode之3SumClosest

布满荆棘的人生 2022-08-05 02:17 215阅读 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).

分析：题目大意是给定一个整型数组，要求求出其中三个数相加的结果与给定的目标值最接近。返回这个值。 还是和上一题差不多，重要的在于定界。

代码:

#include "stdafx.h"
    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    class Solution{
    public:
    	int threeSumClosest(vector<int>& num, int target) {
    		int min_gap = INT_MAX;
    		int result = 0;
    		sort(num.begin(),num.end());
    		auto last = num.end();
    		int sum,gap;
    		for(auto i = num.begin();i < last-2;++i){
    			auto j = next(i);
    			auto k = prev(last);
    			while(j<k){
    				sum = *i + *j + *k;
    				gap = abs(sum - target); //取绝对值
    				if (min_gap > gap){
    					min_gap = gap;
    					result = sum;
    				}
    
    				if (sum > target)
    					--k;
    				else
    					++j;
    			}			
    		}
            return result;
    	}
    };
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	vector<int> v1;
    	int rtn;
    	v1.push_back(-1);
    	v1.push_back(1);
    	v1.push_back(2);
    	v1.push_back(-4);
    
    	Solution s;
    	rtn = s.threeSumClosest(v1, 1);
    	cout << rtn << endl;
    	
    	system("pause");
    	return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 leetcode（3）

最长子串思路：刚开始的时候，想的是可以通过之前的常用比较算法去遍历判断最后发现你这样子太过暴力复杂度应该是O（n 是O（n ³），在参考了大佬的例子后发现了i

系统管理员/ 2023年06月01日 11:29/ 0 赞/ 67 阅读

相关 [Leetcode][第216题][JAVA][数组之和3][回溯]

【问题描述】\[中等\] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6L

ゞ浴缸里的玫瑰/ 2022年12月05日 15:26/ 0 赞/ 176 阅读

相关 leetcode3

Longest SubString Without Repeating Characters 中文翻译，最长无重复字符的子串，返回其长度。最开始的思路就是两重循环。第

约定不等于承诺〃/ 2022年08月08日 17:59/ 0 赞/ 168 阅读

相关 3Sum ---LeetCode

题目： Given an array S of n integers, are there elements a, b, c in S such that a + b +

秒速五厘米/ 2022年08月07日 10:53/ 0 赞/ 213 阅读

相关 LeetCode之3SumClosest

题目： Given an array S of n integers, find three integers in S such that the sum is cl

布满荆棘的人生/ 2022年08月05日 02:17/ 0 赞/ 216 阅读

相关 Leetcode——15. 3Sum

1. 概述 1.1 题目 Given an array S of n integers, are there elements a, b, c in S such

素颜马尾好姑娘i/ 2022年06月14日 09:24/ 0 赞/ 234 阅读

相关 LeetCode之数据结构——数组demo3

代码维护于GitHub：[https://github.com/zrxJuly/data-structure][https_github.com_zrxJuly_data-st

左手的ㄟ右手/ 2022年04月23日 22:12/ 0 赞/ 222 阅读

相关 leetcode（3）

目录 2.两数相加 70.爬楼梯 83.删除有序链表中的重复元素 88合并两个有序的数组 118.杨辉三角 119. 杨辉三角 II 121.买卖股票的最佳时机

Love The Way You Lie/ 2022年03月08日 01:24/ 0 赞/ 190 阅读

相关 LeetCode之3Sum Closest（Kotlin）

> 问题： Given an array nums of n integers and an integer target, find three integers in nu

怼烎@/ 2022年01月20日 11:19/ 0 赞/ 232 阅读

相关 [Leetcode] 3Sum

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

一时失言乱红尘/ 2021年12月03日 07:27/ 0 赞/ 299 阅读