笔试题之算法类(不定期更新。。。)

最近在准备一些面试，突然觉得不能长久的待在一个舒适区里，决定走出去看一看。现将面试过程中或准备过程中碰到的一些笔试题就下来，本篇幅重点记录算法相关，可能大家在其他地方也看到过类似的题或解答，如有错误欢迎指正，如有更好的办法，也请赐教。

一.在指定的int数组中快速找出两两相加等于某个数的所有组合。

1、思路一：拿第一个数与后面所有的数依次相加，依次类推，当满足条件取出。

public  static void foo1(int[] arr,int target){
        for (int i = 0; i < arr.length; i++) {
            for (int j = i+1; j < arr.length - 1; j++) {
                if(arr[i] +arr[j] == target){
                    System.out.println(arr[i] + "," + arr[j]);
                }
            }
        }
    }

缺点：此方式是最耗时，最浪费的。举一个简单的例子：当一个最小的数和一个最大的数相加都无法满足条件时，此时该最小的数与其他数的相加均为无效计算。
2、思路二：在上述基础上，我们首先考虑一下，如何避免出现无效计算。如果我们出现了最小数和最大数的相加都无法满足时，那此时我们应该放弃该最小数的计算，改由第二小的数进行计算。这样的话就需要数组是有序的，能快速找到第二小的数即可。看代码：

 public static void foo2(int[] arr,int target){
        Arrays.sort(arr);
        int low = 0;
        int heigh = arr.length-1;

        while (low < heigh){
            //当大于目标数时，尾部前移
            if(arr[low] + arr[heigh] > target){
                heigh --;
            //当小于目标数时，头部后移
            }else if(arr[low]+ arr[heigh] < target){
                low ++;
            }else {
                low ++;
                heigh --;
                System.out.println(arr[low] + "," + arr[heigh]);
            }
        }
    }