leetcoede两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

链接：

https://leetcode-cn.com/problems/two-sum
双指针做法：时间复杂度（nlog(n)+3n）

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
 var twoSum = function(nums, target) {
    firstnums=JSON.parse(JSON.stringify(nums));
    console.log(firstnums)
   nums.sort((a, b) => a - b);//排序nlog(n)
   console.log(nums)
   let sum;
   let left=0;
   let right=nums.length-1;
    
       while (left < right){//双指针找位置
           sum=nums[left]+nums[right];
           if (sum > target){
               right--;
           }
           else if (sum < target){
               left++;
           }
           else  break;
       }
       console.log(left, right);
   
   for (let i=0;i<nums.length;i++) {//从原始数组前往后找第一个相等
       if (firstnums[i]===nums[left]) {
           left=i; console.log(left);
           break;
       }
   }
   for (let i=nums.length-1;i>=0;i--) {//从原始数组后往前找第一个相等的
    if (firstnums[i]===nums[right]) {
        right=i; console.log(right); break;
    }
    
    }   
   return left<right?[left,right]:[right,left];
};
twoSum([5,75,25],100)

暴力破解：时间复杂度n²

    // 暴力遍历
    // for(let i = 0, len = nums.length; i<len-1; i++) {
    //     for(let j = i+1; j < len; j++) {
    //         if(nums[i] + nums[j] == target){
    //             return [i, j]
    //         }
    //     }
    // 

哈希表：即用Map函数 时间复杂度 O（1）

var twoSum = function(nums, target) {
    let map=new Map();
    for (let i=0; i<nums.length; i++){
        if(map.has(target-nums[i])){
            return [map.get(target-nums[i]),i];
        }
        else{
            map.set(nums[i],i);//键为数组的值，值为数组的索引
        }
    }
}