Leetcode 259. 较小的三数之和（DAY 181）---- 二分查找学习期

た入场券 2022-08-28 10:56 172阅读 0赞

### 文章目录 ###

*   *  原题题目
     *  代码实现（首刷自解 效率较低n^2logn）
     *  代码实现（首刷优化）

--------------------

## 原题题目 ##

--------------------

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16]

--------------------

## 代码实现（首刷自解 效率较低n^2logn） ##

--------------------

class Solution { 
    public:
        int threeSumSmaller(vector<int>& nums, int target) { 
            int left = 0,right = nums.size()-1,ret = 0;
            sort(nums.begin(),nums.end());;
            int size = nums.size();
            for(int i=0;i<size-2;++i)
            { 
                for(int j=i+1;j<size-1;++j)
                { 
                    auto iter = lower_bound(nums.begin()+j+1,nums.end(),target-nums[i]-nums[j]);
                    ret += ((--iter) - nums.begin() - j);
                }
            }
            return ret;
        }
    };

--------------------

## 代码实现（首刷优化） ##

--------------------

class Solution { 
    public:
        int threeSumSmaller(vector<int>& nums, int target) { 
            int left = 0,right = nums.size()-1,ret = 0;
            sort(nums.begin(),nums.end());;
            int size = nums.size();
            for(int i=0;i<size-2;++i)
            { 
                int left = i+1,right = nums.size()-1;
                while(left < right)
                { 
                    int sum = nums[i] + nums[left] + nums[right];
                    if(sum >= target)    --right;
                    else
                    { 
                        ret += right - left;
                        ++left;
                    }
                }
            }
            return ret;
        }
    };

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/24791a38b20c472bb219f88d1c25c48c.png