js實作算法：找出數組中和為給定值的兩個元素

找出數組中和為給定值的兩個元素，

如：[1, 2, 3, 4, 5]中找出和為6的兩個元素

• 暴力法

  首先來分析一下這個題，假設題目沒有說已排序和時間複雜度的要求，那麼用最暴力的方法就是直接周遊兩次數組，時間複雜度為O(N*N)。這裡也來實作一下，代碼如下：

function sameSum(arr, num){
        for (var i =0 ;i<arr.length;i++){
            for (var j = i+1;j<arr.length;j++){
                if (arr[i]+arr[j]==num){
                    console.log('數組中兩個元素和為'+num+'的兩個數為：'+arr[i]+'和'+arr[j]);
                    break;
                }
                //break;
                //如果隻要輸出一組這樣的組合就隻要在内層循環裡break就可以
            }
        }
    }
    var arr =[1,2,3,4];
    sameSum(arr,5);
    //數組中兩個元素和為5的兩個數為：1和4
    //數組中兩個元素和為5的兩個數為：2和3
           

• 降低複雜度方法

  如果題目沒有寫明已排序，那麼可以先将整型數組排序，排序之後定義兩個指針left和right。left指向已排序數組中的第一個元素，right指向已排序數組中的最後一個元素，将 arr[left]+arr[right]與 給定的元素比較，若前者大，right–；若前者小，left++；若相等，則找到了一對整數之和為指定值的元素。此方法采用了排序，排序的時間複雜度為O(NlogN)，排序之後掃描整個數組求和比較的時間複雜度為O(N)。故總的時間複雜度為O(NlogN)，空間複雜度為O(1)。

  代碼如下：

//先将亂序數組排好序
    function bubbleSort(arr){
        var leng = arr.length;
        for(var i =0 ;i<leng;i++){
            for(var j =0;j<leng-i-1;j++){
                if(arr[j]>=arr[j+1]){
                    var temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
        return arr;
    }
    //降低複雜度的方法
    function sameSum(array, num)
    {
        var newArr = bubbleSort(array);
        if(newArr == '' || newArr.length == 0){
            return false;
        }

        var left = 0, right = newArr.length -1;

        while(left < right){
            if(newArr[left] + newArr[right] > num){
                right--;
            }
            else if(newArr[left] + newArr[right] < num){
                left++;
            }
            else{
               console.log('數組中兩個元素和為'+num+'的兩個數為：'+newArr[left]+'和'+newArr[right]);
                left++;
                right--;
            }
        }
    }
    var arr1 = [2,1,4,3,5];
    sameSum(arr1,6);//1 + 5 = 6  2 + 4 = 6