牛客 哔哩哔哩校招编程真题 给定一个整数数组 判断其中是否有3个数和为N 二分经典

题目描述

给定一个整数数组,判断其中是否有3个数和为N

输入描述:

输入为一行

逗号前为一个整数数组，每个元素间用空格隔开；逗号后为N

输出描述:

输出bool值

True表示存在3个和为N的数

False表示不存在3个和为N的数

示例1

输入

复制

1 2 3 4 5,10

输出

复制

True

备注:

数组长度不超过2000，所以数均为int范围的正整数

经典二分题

先用原数组a[]a[~]a[]构造两数之和数组b[]b[~]b[]把b[]b[~]b[]排序扫描一遍a[]a[~]a[]并在b[]b[~]b[]里二分找(K−a[i])(K-a[i])(K−a[i])即可

char ch;while(~scanf("%d%c", &m, &ch)) {a[++n] = m;if(ch == ',') break;}scanf("%d ", &m);for(int i=1; i<=n; i++) // n^2构造b数组for(int j=i+1; j<=n; j++)b[++sz] = a[i] + a[j];sort(b+1, b+1+sz);//别忘了排序for(int i=1; i<=n; i++) {int key = m - a[i];int lef = 1, rig = sz, mid; //二分找m-a[i]while(lef <= rig) {mid = (lef + rig) >> 1;if(b[mid] == key) goto findit;if(b[mid] < key) lef = mid + 1;else rig = mid - 1;}}goto notfind;findit :printf("True");return 0;notfind :printf("False");

完整代码

#define debug#ifdef debug#include <time.h>#include "/home/majiao/mb.h"#endif#include <iostream>#include <algorithm>#include <vector>#include <string.h>#include <map>#include <set>#include <stack>#include <queue>#include <math.h>#define MAXN ((int)1e5+7)#define ll long long #define INF (0x7f7f7f7f)#define fori(lef, rig) for(int i=lef; i<=rig; i++)#define forj(lef, rig) for(int j=lef; j<=rig; j++)#define fork(lef, rig) for(int k=lef; k<=rig; k++)#define QAQ (0)using namespace std;#define show(x...) \do { \cout << "\033[31;1m " << #x << " -> "; \err(x); \} while (0)void err() {cout << "\033[39;0m" << endl; }template<typename T, typename... A>void err(T a, A... x) {cout << a << ' '; err(x...); }namespace FastIO {char print_f[105];void read() {}void print() {putchar('\n'); }template <typename T, typename... T2>inline void read(T &x, T2 &... oth) {x = 0;char ch = getchar();ll f = 1;while (!isdigit(ch)) {if (ch == '-') f *= -1; ch = getchar();}while (isdigit(ch)) {x = x * 10 + ch - 48;ch = getchar();}x *= f;read(oth...);}template <typename T, typename... T2>inline void print(T x, T2... oth) {ll p3=-1;if(x<0) putchar('-'), x=-x;do{print_f[++p3] = x%10 + 48;} while(x/=10);while(p3>=0) putchar(print_f[p3--]);putchar(' ');print(oth...);}} // namespace FastIOusing FastIO::print;using FastIO::read;int n, m, Q, K, a[MAXN], b[MAXN], sz;int main() {#ifdef debugfreopen("test", "r", stdin);// freopen("out_main", "w", stdout);clock_t stime = clock();#endifchar ch;while(~scanf("%d%c", &m, &ch)) {a[++n] = m;if(ch == ',') break;}scanf("%d ", &m);for(int i=1; i<=n; i++) // n^2构造b数组for(int j=i+1; j<=n; j++)b[++sz] = a[i] + a[j];sort(b+1, b+1+sz);//别忘了排序for(int i=1; i<=n; i++) {int key = m - a[i];int lef = 1, rig = sz, mid; //二分找m-a[i]while(lef <= rig) {mid = (lef + rig) >> 1;if(b[mid] == key) goto findit;if(b[mid] < key) lef = mid + 1;else rig = mid - 1;}}goto notfind;findit :printf("True");return 0;notfind :printf("False");#ifdef debugclock_t etime = clock();printf("rum time: %lf 秒\n",(double) (etime-stime)/CLOCKS_PER_SEC);#endif return 0;}

牛客 哔哩哔哩校招编程真题 给定一个整数数组 判断其中是否有3个数和为N 二分经典 三数之和