当前位置：网站首页>leetcode：259. 较小的三数之和

leetcode：259. 较小的三数之和

2022-08-04 14:31:00 【OceanStar的学习笔记】

题目来源

leetcode：259-VIP. 较小的三数之和

题目描述

在这里插入图片描述

class Solution {
    
public:
    int threeSumSmaller(vector<int>& nums, int target){
    

	}
};

题目解析

思路

先对数组排序
固定一个值，然后双指针碰撞。将所有符合条件的[l,r]区间都算到结果里面。

class Solution {
    
public:
    int threeSumSmaller(vector<int>& nums, int target){
    
        int res = 0;
        std::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;
    }
};