马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
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.这道题不能用递归或是深度优先搜索的方法做,会出现重复项,且不能消除。 |