c++刷leetcode（259. 较小的三数之和）【不能用深度优先搜索】
本帖最后由 糖逗 于 2020-4-18 14:17 编辑题目描述：
给定一个长度为 n 的整数数组和一个目标值 target，寻找能够使条件 nums + nums + nums < 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 + nums + nums;
if(sum >= target){
r--;
}
else{
res += r-l;
l++;
}
}
}
return res;
}
注意事项：
1.这道题不能用递归或是深度优先搜索的方法做，会出现重复项，且不能消除。
页:
[1]