大公司面试题 - 算法1

时间：2010-09-05 来源：chouy

最近电话面了个大公司，具体就不说是哪儿啦，电话面试了大概一个小时，都是算法题，面得不太好，主要是电话面，没有用笔什么的。每道题不记效率都可以给个解答方案，但人家要求时间复杂度比较高。我在对方提示下可以把大方面说出来。估计去这个公司复面是没戏了。回去后把第一题题做出来了。下面是题目：

题目描述

给定一个整数序列，判断其中有多少个数，等于数列中其他两个数的和。比如，对于数列1 2 3 4, 这个问题的答案就是2, 因为3 = 2 + 1, 4 = 1 + 3。

下面是我的代码 Base.java -- 这个类只是为了打日志用的

public class Base
{
    public static int debug = 1;

    public void setDebug(int debugLevel)
    {
        Base.debug = debugLevel;
    }

    public static void debug(String str)
    {
        if (1 >= debug)
            System.out.println(str);
    }

    public static void info(String str)
    {
        if (2 >= debug)
            System.out.println(str);
    }

    public static void warn(String str)
    {
        if (3 >= debug)
            System.out.println(str);
    }

    public static void error(String str)
    {
        if (4 >= debug)
            System.out.println(str);
    }
}

下面是解题的类。实现了两种算法，然后在MAIN中对它们的运行时间进行了比较。第一种时间复杂度是O(n^3)，第二种是O(n^2)，大家看一看吧。

import java.util.Arrays;
import java.util.Random;

/**
* <pre>
* 描述
* 给定一个整数序列，判断其中有多少个数，等于数列中其他两个数的和。比如，对于数列1 2 3 4,
* 这个问题的答案就是2, 因为3 = 2 + 1, 4 = 1 + 3。
* 输入
* 第一行是一个整数T，表示一共有多少组数据。 1<= T <= 100
* 接下来的每组数据共两行，第一行是数列中数的个数n ( 1 <= n <= 100)，第二行是由n个整数组成的数列。
*
* 输出
* 对于每组数据，输出一个整数（占一行），就是数列中等于其他两个数之和的数的个数。
* 样例输入
* 2
* 4
* 1 2 3 4
* 5
* 3 5 7 9 10
* 样例输出
* 2
* 1
* </pre>
*
* @author zy
*/
public class HowManyNumIsOthersSum extends Base
{
 static Random random = new Random();

 public static void main(String[] args)
 {
 int max = 10000;
 int length = random.nextInt(max / 2);
 int[] is = new int[length];
 for (int i = 0; i < is.length; i++)
 is[i] = random.nextInt(max);
 HowManyNumIsOthersSum test = new HowManyNumIsOthersSum();
 test.setDebug(1);
 Arrays.sort(is);
 // 先把此序列排序

 info(Arrays.toString(is));
 long start;
 long end;

 start = System.currentTimeMillis();
 test.calc(is);
 end = System.currentTimeMillis();
 info("calc() used " + (end - start) + "ms");

 start = System.currentTimeMillis();
 test.calc2(is);
 end = System.currentTimeMillis();
 info("calc2() used " + (end - start) + "ms");
 }

 public int calc(int[] array)
 {
 // 记录有多少个这样的数

 int total = 0;
 // 然后从第三个开始算起

 for (int i = 2; i < array.length; i++)
 {
 if (isSum(array, i))
 total++;
 }
 info("此数组共有 " + array.length + " 个元素, 共有 " + total + " 组数据满足要求");
 return total;
 }

 /**
 * 第一种算法,全扫描,把每个比它小的两个数相加所是否与其相等
 *
 * @param array
 * @param target
 * 目标数位置
 * @return
 */
 private boolean isSum(int[] array, int target)
 {
 for (int i = 0; i < target - 1; i++)
 {
 for (int j = i + 1; j < target; j++)
 {
 int result = array[i] + array[j];
 if (result == array[target])
 {
 debug(target + " array[" + i + "] + array[" + j + "] = array[" + target + "] " + array[i]
 + " + " + array[j] + " = " + array[target]);
 return true;
 }
 }
 }
 return false;
 }

 /**
 * 第二种算法
 *
 * @param array
 */
 public int calc2(int[] array)
 {
 // 记录有多少个这样的数

 int total = 0;
 // 然后从第三个开始算起

 for (int i = 2; i < array.length; i++)
 {
 if (quickIsSum(array, i))
 total++;
 }
 info("此数组共有 " + array.length + " 个元素, 共有 " + total + " 组数据满足要求");
 return total;
 }

 /**
 * 此数是否是
 *
 * @param array
 * 数组
 * @param target
 * 目标数位置
 * @return
 */
 private boolean quickIsSum(int[] array, int target)
 {
 int t = array[target];
 int left = 0;
 int right = target - 1;
 while (left < right)
 {
 int sum = array[left] + array[right];
 if (sum == t)
 {
 debug(target + " array[" + left + "] + array[" + right + "] = array[" + target + "] "
 + array[left] + " + " + array[right] + " = " + t);
 return true;
 }
 else if (sum < array[target]) // 和小于目标

 {
 left++;
 }
 else // 和大于目标

 {
 if (array[left] + array[left] > t)
 {
 return false;
 }
 right--;
 }
 }
 return false;
 }
}

如果把代码中的debug全注释掉，速度会更快。

我不知道还有没有更快速的算法，如果有，请回复给我代码。

其它几题近期贴出，谢谢关注。