By yusijia

Updated:

Contents
  1. 1. 题目：

题目：

一个数组里找两个相加和为N的组合

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
1.另外开两个数组，不允许重复
//用一个辅助数组和一个标记数组
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <string>
#include <algorithm>

using namespace std;

int a[100], b[100], mark[100];

int main()
{
    int m, k;
    scanf("%d", &m);
    scanf("%d", &k);
    //默认输入排好序的数组
    for(int i = 0; i < m; i++){
        mark[i] = 0;            //0代表没输出过，1代表输出过了
        scanf("%d", &a[i]);
        b[i] = k - a[i];        //存要找的k - a[i]
    }

    int L = 0, R = m - 1;

    while(L < m && R >= 0){
        if(b[R] < a[L]){
            R--;
        }else if(b[R] > a[L]){
            L++;
        }else if(mark[L] == 0 && mark[R] == 0 && b[R] == a[L]){//mark[L] == 0 && mark[R] == 0 用于防止重复
            printf("%d %d\n", a[L], k - a[L]);
            mark[L++] = 1, mark[R--] = 1;
        }
    }

    return 0;
}


//////////////////////////////////////////////
2.只用一个数组, 允许重复
#include <cstdio>

int k, n;
int a[100];

int main()
{
    scanf("%d%d", &n, &k);
    for(int i = 0; i < n; i++){
        scanf("%d", &a[i]);
    }
    int L = 0, R = n - 1;
    while(L < R){
        int data = k - a[R];
        if(a[L] == data){
            printf("%d %d\n", a[L++], a[R--]);
        }else if(a[L] < data){
            L++;
        }else if(a[L] > data){
            R--;
        }
    }
    return 0;
}


/////////////////////////////
3.只用一个数组, 不允许重复
#include <cstdio>

int k, n;
int a[100];

int main()
{
    scanf("%d%d", &n, &k);
    for(int i = 0; i < n; i++){
        scanf("%d", &a[i]);
    }
    int L = 0, R = n - 1;
    while(L < R){
        int data = k - a[R];
        if(a[L] == data){
            printf("%d %d\n", a[L++], a[R--]);
            while(L < R && a[L] == a[L - 1])
                L++;
            while(L < R && a[R] == a[R + 1])
                R--;
        }else if(a[L] < data){
            L++;
        }else if(a[L] > data){
            R--;
        }
    }
    return 0;
}
Contents
  1. 1. 题目：