LeetCode之3SumClosest

布满荆棘的人生 2022-08-05 02:17 150阅读 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 条评论，150人围观）

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

相关阅读

相关 leetcode（3）

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

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

相关【leetcode系列】3Sum

这个题我最开始的思路是：先一个数定下来，然后在除这个数之外的集合里面找另外两个数，最后计算和。如此反复，对于N个数，需要进行N-2次循环。我遇到的问题就是怎么找另外两个数，

灰太狼/ 2022年08月10日 17:34/ 0 赞/ 126 阅读

相关 leetcode3

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

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

相关 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 赞/ 154 阅读

相关 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 赞/ 151 阅读

相关 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 赞/ 167 阅读

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

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

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

相关 leetcode（3）

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

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

相关 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 赞/ 162 阅读

相关 [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 赞/ 220 阅读