【数组】Two Sum

题目：

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

思路：

　　首先对数组排序。不过由于最后返回两个数字的索引，所以需要事先对数据进行备份。然后采用2个指针l和r，分别从左端和右端向中间运动：当l和r位置的两个数字之和小于目标数字target时，r减1；当l和r位置的两个数字之和大于目标数字target时，l加1。因此只需扫描一遍数组就可以检索出两个数字了。最后再扫描一遍原数组，获取这两个数字的索引。

 var twoSum = function(nums, target) {

            var temp=[];

            var index=[];

            for(var i=0;i<nums.length;i++){

                temp[i]=nums[i];

            }

            temp.sort(function(a,b){return a-b;});

            var l=0,r=temp.length-1;

            while(l<r){

                if(temp[l]+temp[r]==target){

                    break;

                }else if(temp[l]+temp[r]>target){

                    r--;

                }else{

                    l++;

                }

            }

            for(var i=0,n=2;i<nums.length;i++){

                if(nums[i]==temp[l]||nums[i]==temp[r]){

                    index.push(i+1);

                    --n;

                    if(n==0){

                        break;

                    }

                }

            }

            return index;

        };

巴特西

【数组】Two Sum

最新文章

热门文章