一个排好序的数组，找出两数之和为m的所有组合

• 不论原序列是有序还是无序，解决这类题有以下三种办法：1、二分（若无序，先排序后二分），时间复杂度总为O（n*logn），空间复杂度为O（1）；2、扫描一遍X-S[i]  映射到一个数组或构造hash表，时间复杂度为O（n），空间复杂度为O（n）；3、两个指针两端扫描（若无序，先排序后扫描），时间复杂度最后为：有序O（n），无序O（n*logn+n）=O（n*logn），空间复杂度都为O（1）。
• 所以，要想达到时间O（N），空间O（1）的目标，除非原数组是有序的（指针扫描法），不然，当数组无序的话，就只能先排序，后指针扫描法或二分（时间n*logn，空间O（1）），或映射或hash（时间O（n），空间O（n））。时间或空间，必须牺牲一个，自个权衡吧。
• 综上，若是数组有序的情况下，优先考虑两个指针两端扫描法，以达到最佳的时（O（N）），空（O（1））效应。否则，如果要排序的话，时间复杂度最快当然是只能达到N*logN，空间O（1）则是不在话下

<?php
$arr=range(1,10);
$m=11;

/**
 * 时间复杂度o(n*n)
 * @param unknown_type $m
 * @param unknown_type $arr
 * 思路1：直接穷举，从数组中任意选取两个数，判定它们的和是否为输入的那个数字。
 * 此举复杂度为O（N^2）。很显然，我们要寻找效率更高的解法。
 */
function getM($m,$arr){
    //print_r($arr);

    $len=count($arr);
    for($i=0;$i<$len;$i++){
        for($j=$i+1;$j<$len;$j++){
            if(($arr[$i]+$arr[$j])==$m){
                //echo 'aaaaaaaaa';

                echo "($arr[$i]+$arr[$j]=${m})".'';
            }
        }
    }
}
/**
 *方法2
 * @param unknown_type $m
 * @param unknown_type $arr
 * 如果数组是无序的，先排序（n*logn），然后用两个指针i，j，各自指向数组的首尾两端，
 * 令i=0，j=n-1，然后i++，j--，逐次判断a[i]+a[j]?=sum，如果某一刻a[i]+a[j]>sum，
 * 则要想办法让sum的值减小，所以此刻i不动，j--，如果某一刻a[i]+a[j]
 * 法让sum的值增大，所以此刻i++，j不动。所以，数组无序的时候，时间复杂度最终为
 * O（n*logn+n）=O（n*logn），若原数组是有序的，则不需要事先的排序，直接O（n）
 * 搞定，且空间复杂度还是O（1），此思路是相对于上述所有思路的一种改进。
 */
function getM2($m,$arr){
    $len=count($arr);
    $i=0;
    $j=$len-1;
    while($i<$j){
        if(($arr[$i]+$arr[$j])>$m){
            $j--;
            continue;
        }
        if(($arr[$i]+$arr[$j])<$m){
            $i++;
            continue;
        }
        if(($arr[$i]+$arr[$j])==$m){
            echo "($arr[$i]+$arr[$j]=${m})".'';
            $i++;
            $j--;
            continue;
        }
    }
}
$t1=time();
 getM($m,$arr);
 $t2=time();
 echo 't1耗时:'.($t2-$t1).'';
getM2($m,$arr);
$t3=time();
echo 't2耗时:'.($t3-$t2).'';
?>