Leetcode 剑指 Offer 57. 和为s的两个数字（DAY 174）---- 二分算法学习期

怼烎@ 2022-09-12 12:44 76阅读 0赞

### 文章目录 ###

*   *  原题题目
     *  代码实现（首刷自解）
     *  代码实现（首刷优化算法）

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

## 原题题目 ##

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

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

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

## 代码实现（首刷自解） ##

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

class Solution { 
    public:
        vector<int> twoSum(vector<int>& nums, int target) { 
            vector<int> ret;
            for(int i=0;i<nums.size();++i)
            { 
                auto iter = lower_bound(nums.begin()+i,nums.end(),target - nums[i]);
                if(iter == nums.end() || *iter != target-nums[i])
                    continue;
                else
                { 
                    ret.emplace_back(nums[i]);
                    ret.emplace_back(target-nums[i]);
                    break;
                }
            }
            return ret;
        }
    };

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

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

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

class Solution { 
    public:
        vector<int> twoSum(vector<int>& nums, int target) { 
            vector<int> ret;
            int left = 0,right = nums.size()-1;
            while(left < right)
            { 
                int sum = nums[left] + nums[right];
                if(sum == target)
                { 
                    ret.emplace_back(nums[left]);
                    ret.emplace_back(nums[right]);
                    break;
                }
                else if(sum > target) --right;
                else ++left;
            }
            return ret;
        }
    };

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/b9e5c5237d4e4a388f586708b4d78182.png