[编程题]找出有序数组中和为sum的两个数
var n = parseInt(readline());
var line = readline().split(" ");
var arr = [];
for(var i=0;i<n;i++){
arr[i] = parseInt(line[i]);
}
var sum = parseInt(readline());
var left = 0,right = n-1;
var str = "";
while(left<right){
var temp = arr[left]+arr[right];
if(temp<sum){
left++;
}else if(temp>sum){
right--;
}else{
str = arr[left] + " " + arr[right];
break;
}
}
if(str){
console.log(str);
}else{
console.log("notfound");
}
发表于 2020-08-13 14:47:11
回复(0)
JavaScript(Node) 😎题目:bilibili📺-两数之和
leetcode 1 twosum
const readline = require('readline')
const rl = readline.createInterface({
input: process.stdin,
ouput: process.stdout
})
let inArr = []
rl.on('line',line=>{
if(!line) return
inArr.push(line.trim())
if(inArr.length === 3){
let arr = inArr[1].split(' ').map(e=>+e)
let sum = +inArr[2]
console.log(twoSum(arr,sum))
}
})
function twoSum (arr, sum) {
let len = arr.length
let i = 0
let j = len - 1
if (len<2) return "notfound"
while(i<j) {
let res = arr[i] + arr[j]
if (res === sum) return [arr[i], arr[j]].join(' ')
if (res > sum) {
j--
}
if (res < sum) {
i++
}
}
return "notfound"
}
发表于 2020-02-27 13:48:21
回复(0)
双指针法
#include<iostream>
using namespace std;
int main()
{
int k;
scanf("%d",&k);
int a[k];
for(int i = 0; i < k ; i++)
scanf("%d",&a[i]);
int s;
scanf("%d",&s);
int i = 0,j = k - 1;
while(i<j)
{
if(a[i] + a[j] == s)
{
printf("%d %d",a[i],a[j]);
return 0;
}
else if(a[i] + a[j] > s) j -- ;
else i ++ ;
}
printf("notfound\n");
return 0;
}
编辑于 2019-11-29 17:21:35
回复(0)
function solve (arr, target) {
let i = 0
let j = arr.length - 1
let first, last
while (i < j) {
first = arr[i]
last = arr[j]
const sum = first + last
if (sum === target) return [first, last]
else if (sum > target) j--
else i++
}
return null
}
发表于 2020-03-03 15:47:52
回复(0)
javascript(V8) 58ms
实现思路：用一个对象的key来存储遍历过的数字（value值任意，这里用的是0），每次循环只需判断(sum-当前值)的key值对应的value是不是为0（为0就代表之前遍历过这个数字）
因为只用到一个for循环，时间复杂度为O(n)
let length = parseInt(readline()),
arg = readline().split(" "),
sum = parseInt(readline()),
temp = {},// 用来存储遍历过的数字的对象
flag = 0;
for(let i = 0; i < length; i++) {
let a = arg[i];
let b = sum - a;
temp[a] = 0;
if(temp[b] === 0) {
console.log(b+" "+a);
flag = 1;
break;
}
}
if(flag === 0) {
console.log("notfound");
}
发表于 2020-04-15 21:47:46
回复(0)
#include<iostream>
#include<cstdio>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<time.h>
#include<algorithm>
using namespace std;
int main(){
int n ;
cin>>n;
int a[n];
for(int i = 0 ;i<n;i++){
cin>>a[i];
}
int sum;
cin>>sum;
int o = 1;
int j;
for( j = 0; j < n-1 ;j++){
if(a[j]+a[o++]==sum){
cout<<a[j]<<" "<<a[--o]<<endl;
break;
}
}
if(j == n-1){
cout<<"notfound"<<endl;
}
return 0;
}
#include<cstdio>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<time.h>
#include<algorithm>
using namespace std;
int main(){
int n ;
cin>>n;
int a[n];
for(int i = 0 ;i<n;i++){
cin>>a[i];
}
int sum;
cin>>sum;
int o = 1;
int j;
for( j = 0; j < n-1 ;j++){
if(a[j]+a[o++]==sum){
cout<<a[j]<<" "<<a[--o]<<endl;
break;
}
}
if(j == n-1){
cout<<"notfound"<<endl;
}
return 0;
}
发表于 2021-08-23 15:59:32
回复(0)
第一次做面试编程题，如何获取网站测试用例的值啊，代码运行没问题，网站的测试用例跟自己的用例总是不一致导致不通过好头疼啊
发表于 2021-03-18 11:00:01
回复(0)
const n = parseInt(readline());
const arr = readline().split(' ').map(Number);
const target = parseInt(readline());
const test = (arr, target) => {
const map = new Map();
const len = arr.length;
for (let i = 0; i < len; i++) {
if (map.has(arr[i])) {
return [arr[map.get(arr[i])], arr[i]]
} else {
map.set(target - arr[i], i)
}
}
}
const a = test(arr, target);
if (!a || !a.length) {
console.log('notfound');
} else {
console.log(a[0], a[1]);
}
发表于 2020-10-17 20:26:05
回复(0)
双指针问题。
#include<iostream>
using namespace std;
int main(void){
int a;
int n;
cin >> a;
int arr[1000000];
for(int i = 0; i < a; i++){
cin >> arr[i];
}
cin >> n;
int begin = 0;
int end = a - 1;
while(begin < end){
if(arr[begin] + arr[end] == n){
cout << arr[begin] << " " << arr[end];
return 0;
}else if(arr[begin] + arr[end] > n){
end--;
}
begin++;
}
cout << "notfound";
return 0;
}
发表于 2020-09-20 23:49:31
回复(0)
function getSum(len, arr, sum) {
if (len < 2) {
return 'notfound'
}
for (var i = 0; i < len; i++) {
for (var j = i + 1; j < len; j++) {
if (arr[i] + arr[j] == sum) {
return arr[i] + ' ' + arr[j]
}
}
}
return 'notfound'
}
编辑于 2020-04-29 21:32:04
回复(1)
import java.util.Scanner;
public class Main{
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scanner=new Scanner(System.in);
int size=scanner.nextInt();
int f[]=new int[size];
for(int i=0;i<size;i++)
f[i]=scanner.nextInt();
int sum=scanner.nextInt();
int left=0;
int right=size-1;
int state=0; // 用于判断状态
while(left<right) {
while(left<right&&f[right]+f[left]>sum) {
right--;
}
while(f[left]+f[right]<sum && left<right) {
left++;
}
if(f[left]+f[right]==sum)
break;
}
if(left<right)
System.out.println(f[left]+" "+f[right]);
else
System.out.println("notfound");
}
}
public class Main{
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scanner=new Scanner(System.in);
int size=scanner.nextInt();
int f[]=new int[size];
for(int i=0;i<size;i++)
f[i]=scanner.nextInt();
int sum=scanner.nextInt();
int left=0;
int right=size-1;
int state=0; // 用于判断状态
while(left<right) {
while(left<right&&f[right]+f[left]>sum) {
right--;
}
while(f[left]+f[right]<sum && left<right) {
left++;
}
if(f[left]+f[right]==sum)
break;
}
if(left<right)
System.out.println(f[left]+" "+f[right]);
else
System.out.println("notfound");
}
}
发表于 2020-03-23 12:32:05
回复(0)
function func (arr, sum) {
const length = arr.length;
if (length<2) return false;
let i = 0;
let j = length - 1;
while(i<j) {
let res = arr[i] + arr[j];
if (res === sum) return [arr[i], arr[j]];
if (res > sum) {
j--;
}
if (res < sum) {
i++;
}
}
return false;
}
const length = arr.length;
if (length<2) return false;
let i = 0;
let j = length - 1;
while(i<j) {
let res = arr[i] + arr[j];
if (res === sum) return [arr[i], arr[j]];
if (res > sum) {
j--;
}
if (res < sum) {
i++;
}
}
return false;
}
发表于 2019-12-14 13:28:07
回复(0)
function getSum (length, arr, sum) {
let arr1 = []
if(length < 2) {
return'notfound'
} else{
for(let i = 0;i < length; i++) {
for(let j = i;j < length; j++) {
if(arr[j] == sum - arr[i]){
returnarr[i], arr[j]
} else{
return'notfound'
}
}
}
}
}
发表于 2019-11-29 14:41:56
回复(1)
问题信息
通过挑战的用户
-
2022-11-29 15:00:36 -
2022-11-02 21:22:20 -
2022-11-02 21:04:15
-
2022-10-15 21:33:03
-
2022-09-28 17:25:07
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
