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