和为给定数

题意

在整数序列中找一对数使其和为给定值；有多组时输出较小数最小的一组。

思路

先升序排序。左右指针的和偏小时左指针右移，偏大时右指针左移；相等时直接输出。左指针从最小数开始推进，因此第一次找到的数对具有最小的较小数。

代码

Python代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16input()
numbers = sorted(map(int, input().split()))
target_sum = int(input())

left, right = 0, len(numbers) - 1
while left < right:
    current_sum = numbers[left] + numbers[right]
    if current_sum == target_sum:
        print(numbers[left], numbers[right])
        break
    if current_sum < target_sum:
        left += 1
    else:
        right -= 1
else:
    print("No")

C++代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;

ll n,sum;
ll a[100005];
void init(){
    scanf("%lld",&n);
    int i;
    for (i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    scanf("%lld",&sum);
}

//查找范围是[l,r), a[r] 永远 >= key
template <typename T>
int first_ge(T key,T a[],int l,int r){
    int m;
    while( l != r  ) //表示l和r没有重合
    {
        m = (l+r) >>1; // 取中间位置
        if( a[m] < key ) //表示 [m+1,r) 满足条件
            l = m+1;
        else
            r = m;
    }
    return l;
}

int main(){
    init();
    sort(a+1,a+n+1);
    int i;
    for(i=1;i<=n;i++){
        ll ret = sum - a[i];
        int pos = first_ge(ret,a,i+1,n+1);
        if( a[pos] == ret){
            printf("%lld %lld\n",a[i],a[pos]);
            return 0;
        }
    }
    printf("No");
    return 0;
}

复杂度

排序为 $O(n \log n)$ ，双指针扫描为 $O(n)$ ，空间复杂度为 $O(n)$ 。

总结

有序序列中的两数之和可通过一增一减的双指针在线性时间内完成。

目录

题意

思路

代码

Python代码

C++代码

复杂度

总结