(ACM)三数较小之和

亦凉 2022-05-04 04:30 163阅读 0赞

**题目描述:**

给定一个包含n(n <= 2000)个整数的无序数组,在数组中选三个数使得它们的和小于一个特殊的数,每个数字只能使用一次

请实现three\_sum\_smaller函数,传入的nums是数组,length是元素的个数,target表示选出来的三个数的和需要小于target。返回一个整数,表示返回方法的种类数

样例输入:

10 35
    19 28 23 1 30 15 7 15 21 5

样例输出:

17

解题思路:暴力搜索+二分查找的联合使用,时间复杂度:n\*n\*log2n

首先对数组进行排序,然后通过暴力搜索的方法,选取第一个数num1(左边)和第二个数num2(中间),得到要查找的第三个数

Sum = Target - num1 - num2

然后我们通过二分查找法,查找第一个大于等于sum的数(lower\_bound方法)

得到下标后,num3的下标减去num2的下标+1就是所需的结果

部分实现代码如下:

int lower_bound(vector<int> &nums, int left, int right, int x) {   //不存在则返回最后一个元素
    	int mid;
    	while (left < right) {
    		mid = (left + right) / 2;
    		if (nums[mid] >= x) {
    			right = mid;
    		}
    		else {
    			left = mid + 1;
    		}
    	}
    	
    	return left;
    }
    
    int three_sum_smaller(vector<int> &nums, int length, int target) {
    	quick_sort(nums, 0, length-1);  //先排个序
    	int count = 0;
    	for (int i = 0; i < length; i++) {
    		for (int j = i + 1; j < length; ++j) {
    			int sum = target - nums[i] - nums[j];
    			int k = lower_bound(nums, j + 1, length-1, sum);
    			count += k - i;
    		}
    	}
    	return count;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关两数之和、三数之和、四数之和、K数之和

数之和、三数之和、四数之和和K数之和是最近听室友提起的几道有意思的基础题，可以说是把双指针运用的淋漓尽致。（K数之和其实是一个动态规划的题，此处因为满足`*数之和`的的结...

淡淡的烟草味﹌/ 2024年04月17日 19:48/ 0 赞/ 109 阅读

相关三数之和

题目：给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组

「爱情、让人受尽委屈。」/ 2023年10月02日 12:57/ 0 赞/ 35 阅读

相关 leetcode259. 较小的三数之和

给定一个长度为 n 的整数数组和一个目标值 target，寻找能够使条件 nums\[i\] + nums\[j\] + nums\[k\] < target 成立的三元组 i

喜欢ヅ旅行/ 2023年07月03日 10:43/ 0 赞/ 1 阅读

相关三数之和

每日一题–三数之和今天来看一道三数之和的面试题，思路比较简单，直接看题。题目描述　　给定一个数组和一个目标值，从数组中找到三个值，使其和最接近目标值。

逃离我推掉我的手/ 2023年02月27日 10:36/ 0 赞/ 22 阅读

相关三数之和

一、前言问题来源LeetCode 问题链接：[https://leetcode-cn.com/explore/interview/card/bytedance/243

小灰灰/ 2023年02月18日 09:33/ 0 赞/ 17 阅读

相关三数之和

public class ThreeNumSum { //NC54 三数之和 https://www.nowcoder.com/practice/345e2

àì夳堔傛蜴生んèń/ 2023年01月21日 11:15/ 0 赞/ 21 阅读

相关三数之和

三数之和 1、参考资料 https://leetcode-cn.com/problems/3sum/ https://leetcode-cn.com/proble

深碍√TFBOYSˉ_/ 2022年12月03日 09:13/ 0 赞/ 149 阅读

相关 Leetcode 259. 较小的三数之和（DAY 181）---- 二分查找学习期

文章目录原题题目代码实现（首刷自解效率较低n^2logn）代码实现（首刷优化） --------------------

た入场券/ 2022年08月28日 10:56/ 0 赞/ 187 阅读

相关 leetcode 两数之和、三数之和、最接近的三数之和、四数之和

两数之和题目链接：[两数之和][Link 1] 给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。你可以假设每个输入只对应一种答案，且同样的元素不能被重

缺乏、安全感/ 2022年05月25日 06:46/ 0 赞/ 356 阅读

相关 (ACM)三数较小之和

题目描述: 给定一个包含n(n <= 2000)个整数的无序数组,在数组中选三个数使得它们的和小于一个特殊的数,每个数字只能使用一次请实现three\_sum\_smal

亦凉/ 2022年05月04日 04:30/ 0 赞/ 164 阅读