c++刷leetcode（259. 较小的三数之和）【不能用深度优先搜索】

糖逗

题目描述：

1. 
   
2. 给定一个长度为 n 的整数数组和一个目标值 target，寻找能够使条件 nums[i] + nums[j] + nums[k] < target 成立的三元组  i, j, k 个数（0 <= i < j < k < n）。
   
3. 
   
4. 示例：
   
5. 
   
6. 输入: nums = [-2,0,1,3], target = 2
   
7. 输出: 2
   
8. 解释: 因为一共有两个三元组满足累加和小于 2:
   
9.      [-2,0,1]
   
10.      [-2,0,3]
    
11. 进阶：是否能在 O(n2) 的时间复杂度内解决？

复制代码

1. int threeSumSmaller(vector<int>& nums, int target) {
   
2.         int res = 0;
   
3.         sort(nums.begin(), nums.end());
   
4.         for(int i = 0; i < nums.size(); i++){
   
5.             int l = i+1, r = nums.size()-1;
   
6.             while(l<r){
   
7.                 int sum = nums[i] + nums[l] + nums[r];
   
8.                 if(sum >= target){
   
9.                     r--;
   
10.                 }
    
11.                 else{
    
12.                     res += r-l;
    
13.                     l++;
    
14.                 }
    
15.             }
    
16.         }
    
17.         return res;
    
18. 
    
19.     }

复制代码

注意事项：
1.这道题不能用递归或是深度优先搜索的方法做，会出现重复项，且不能消除。