找出有序数组中和为sum的两个数

[编程题]找出有序数组中和为sum的两个数

热度指数：3294 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

找出有序数组（从小到大排列）中和为sum的两个数，要求复杂度为O(n)，找到一组即可

输入描述:

第一行：数组长度
第二行：数组各项的值
第三行：sum

输出描述:

若存在，输出和为sum的两个数，以空格分隔；若不存在，输出notfound

示例1

输入

5
1 3 4 6 8
10

输出

4 6

示例2

输入

5
1 3 4 6 8
13

输出

notfound

算法知识视频讲解

JavaScript

牛客871077581号

		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)

JavaScript

牛客522196877号

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)