一道算法优化题，求有序数组是否存在两数之和等于第三个给定的数字

问题描述

问 题

1.题：给出一个函数，判断在一个给定的有序数组中，是否存在两个数之和等于给定的第三个数。

这道题本身挺简单，但是如果直接使用嵌套两个 for 循环的方式去做的话，时间复杂度非常之高。

希望能有大牛给出一个简单的算法优化思路。

解决方案

经典的two sum problem，保存双指针，分别指向数组开头和末尾，假设数组非降序排列，分情况讨论：

1. 如果当前两个数的和等于给定值，成功。

2. 如果当前两个数的和小于给定值，头指针右移。

3. 如果当前两个数的和大于给定值，尾指针左移。

如果尾指针跑到了头指针左边则无解。

时间复杂度O(N)

也有其他解法，还有3 / 4 sum problem，很容易搜到。

参考：
http://stackoverflow.com/questions/11928091/linear-time-algorithm-for-2-sum
https://leetcode.com/problems/two-sum/

这篇关于一道算法优化题，求有序数组是否存在两数之和等于第三个给定的数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！