首页 > 代码库 > 剑指offer (41) 有序数组数字之和

剑指offer (41) 有序数组数字之和

2024-07-09 18:52:59   216人阅读

题目：输入一个递增排序的数组和一个数字target，在数组中查找两个数使得它们的和正好是target

 

题解分析：

一提到有序数组，应该立马联想到 二分查找

因为数组已经有序了，我们可以设置两个游标first和last，下标first指向 0, last指向 size() - 1, 然后相加

如果 相加和 大于 target，last--

如果 相加和 小于 target，first++

T(n) = O(n)

void TwoSum(const std::vector<int>& num, int target, std::vector<std::vector<int>>& result) {    if (num.size() < 2) return;        int first = 0;    int last  = num.size() - 1;    while (first < last) {        int sum = num.at(first) + num.at(last);        if (sum < target) {            ++first;        } else if (sum > target) {            --last;        } else {            std::vector<int> tmp = {num.at(first), num.at(last)};            result.push_back(tmp);            ++first;            --last;        }    }}

 

题目二：输入一个正整数s，打印出所有和为s的连续整数序列(至少含两个数)

例如 target = 15：

1+2+3+4+54+5+67+8

 

题解分析：

step1. 分别使用两个游标指示 当前序列的最小值和最大值，即 first游标指示 当前序列的第一个数，last游标指示 当前序列的最后一个数

step2. sum = first + last

step3. 

如果 sum < target, 则需要last向右扩充一步使得当前序列和增大，即先++last，然后更新sum

如果 sum > target, 则需要first向右扩充一步使得当前序列和减小，这时需要先更新sum，然后--first

 

void Sum(int target, std::vector<std::vector<int>>& result){    int first = 1;    int last  = 2;    int sum = first+ last;    while (first < last && first <= target / 2) {        if (sum < target) {            ++last;            sum += last;        } else if (sum > target) {            sum -= first;            ++first;        } else {            std::vector<int> temp(last - first + 1, 0);            for (int i = 0; i < last - first + 1; ++i) {                temp.at(i) = (first + i);            }            result.push_back(temp);            ++last;            sum += last;        }    }}

 


联系
我们