面试-算法 已经排好序的数组中求两个数的和等于N

已知一个拍好序的数组，长度为M

在其中找两个数，其和为N

 

刚刚拿到这个题目的时候，首先的常规想法是遍历循环求出所有数的和，最终其值为N的就是结果,这个算法时间复杂度为o(N*N)

可能还有一些扩展的想法，那就是先把数组中比N大的元素去掉，这样少检查几个元素

这是典型的程序员思维，太早开始考虑实现细节了

作为一个算法题目首先要把算法复杂度降低下来，然后再考虑常数C。。。不要太早开始考虑这种相对不重要的问题

 

由于要寻找的是一个数对，假设这里存在解的话，考虑用N减去数组中的每一个值

生成一个新数组M2，假设M2的值在M中出现，那么就可以找到解，（用两个指针 一个从M的左边 一个从M2的右边）

算法复杂度可以做到o(N)

 

代码如下

        public static void Test()
        {
            List<int> array = new List<int>() { 1, 2, 3, 4, 5, 6, 5, 6, 565, 33, 35, 7, 9, 33, 4, 12, 13, 14, 15, 16, 17, 18, 19, 02, 234, 23, 45, 46, 48 };
            array.Sort();
            Test1(array.ToArray());
        }
public static void Test1(int[] array)
        {
int N = 49;
int[] array2 = new int[array.Length];

for (int i = 0; i < array.Length; i++)
            {
                array2[i] = N - array[i];
            }

int startI = 0;
int startJ = array.Length - 1;
while ((startI != array.Length - 1) || (startJ != 0))
            {
if (array[startI] == array2[startJ])
                {
                    Console.Write(startI + ":" + array[startI] + "+" + startJ + ":" + array[startJ]);
return;
                }
else if (array[startI] > array2[startJ])
                {
                    startJ--;
                }
else
                {
                    startI++;
                }
            }
        }
    }