|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
本帖最后由 糖逗 于 2020-4-18 14:17 编辑
题目描述:
- 给定一个长度为 n 的整数数组和一个目标值 target,寻找能够使条件 nums[i] + nums[j] + nums[k] < target 成立的三元组 i, j, k 个数(0 <= i < j < k < n)。
- 示例:
- 输入: nums = [-2,0,1,3], target = 2
- 输出: 2
- 解释: 因为一共有两个三元组满足累加和小于 2:
- [-2,0,1]
- [-2,0,3]
- 进阶:是否能在 O(n2) 的时间复杂度内解决?
复制代码
- int threeSumSmaller(vector<int>& nums, int target) {
- int res = 0;
- sort(nums.begin(), nums.end());
- for(int i = 0; i < nums.size(); i++){
- int l = i+1, r = nums.size()-1;
- while(l<r){
- int sum = nums[i] + nums[l] + nums[r];
- if(sum >= target){
- r--;
- }
- else{
- res += r-l;
- l++;
- }
- }
- }
- return res;
- }
复制代码
注意事项:
1.这道题不能用递归或是深度优先搜索的方法做,会出现重复项,且不能消除。 |
|