(ACM)三数较小之和

亦凉 2022-05-04 04:30 118阅读 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 条评论，118人围观）

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

相关阅读

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

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

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

相关【LeetCode】两数之和、三数之和、四数之和系列

文章目录两数之和★ 三数之和★★ 四数之和★★ 四数相加Ⅱ★★

r囧r小猫/ 2022年12月26日 04:49/ 0 赞/ 186 阅读

相关三数之和

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

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

相关 LeetCode 之两数之和 + 三数之和 + 四数之和

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5reY5reY5piv5

冷不防/ 2022年09月12日 02:53/ 0 赞/ 206 阅读

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

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

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

相关【lintcode】两数之和、三数之和、最接近的三数之和、四数之和小结

两数之和给一个整数数组，找到两个数使得他们的和等于一个给定的数 target。你需要实现的函数twoSum需要返回这两个数的下标, 并且第一个下标小于

不念不忘少年蓝@/ 2022年06月05日 06:53/ 0 赞/ 213 阅读

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

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

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

相关 acm 数数小木块

数数小木块时间限制：3000 ms | 内存限制：65535 KB 难度：1 输入第一行是一个整数N(N<=10)表示测试数据的组数）接下来的n行每

Love The Way You Lie/ 2022年05月17日 12:14/ 0 赞/ 147 阅读

相关 (ACM)三数较小之和

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

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

相关 LeetCode 两数之和、三数之和

1. 两数之和给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的两个整数。你可以假设每种输入只会对应一个答案。但是，你不能重复

旧城等待，/ 2022年04月13日 05:42/ 0 赞/ 250 阅读