js 무질서 배열 의 두 수의 합 - 힘 의 단 추 를 실현 합 니 다.

목차
1 문제
2 입 출력
3 해법
1) 폭력 법
2) 대상 또는 ES6 에서 맵 데이터 구 조 를 공간 으로 시간 을 바 꾸 는 방법
3）
4 코드
1 문제
https://leetcode-cn.com/problems/two-sum/
정수 배열 nums 지정 목표 치 target 과 함께 이 배열 에서 목표 치 를 찾 아 보 세 요. 두 개의 정수 와 그들의 배열 로 돌아 가 표 시 를 한다.
너 는 모든 입력 이 하나의 답안 에 만 대응 할 것 이 라 고 가정 할 수 있다.그러나 배열 의 같은 요 소 는 두 번 사용 할 수 없다.
2 입 출력
예시:
주어진 nums = [2, 7, 11, 15], target = 9
왜냐하면 nums [0] + nums [1] = 2 + 7 = 9
그래서 [0, 1] 로 돌아 갑 니 다.
3 해법
1) 폭력 법
모든 요소 x 를 옮 겨 다 니 며 target - x 와 같은 목표 요소 가 있 는 지 찾 습 니 다.이곳 은 이중 순환 으로 실현 할 수 있다.
시간 복잡 도: O (n2) 즉 n 방
공간 복잡 도: O (1)
2) 대상 또는 ES6 에서 맵 데이터 구 조 를 공간 으로 시간 을 바 꾸 는 방법
운행 시간의 복잡 도 를 최적화 하기 위해 서 우 리 는 배열 에 목표 요소 가 존재 하 는 지 확인 하 는 더욱 효과 적 인 방법 이 필요 하 다.만약 존재 한다 면, 우 리 는 그것 의 색인 을 찾 아야 한다.
공간 으로 속 도 를 바 꾸 는 방식 으로 대상 이나 ES6 에서 Map 데이터 구조 조회 속도 가 for 조회 보다 빠르다.nums 배열 값 은 키 로 하고 값 은 아래 표 시 며 구축 대상 이나 Map 입 니 다.배열 nums 에 대해 모든 요소 x 를 옮 겨 다 니 며 target - x 와 같은 목표 요소 가 존재 하 는 지 찾 습 니 다. 같 으 면 결 과 를 얻 고 같 지 않 으 면 값 을 키 로 하고 아래 표 시 를 대상 이나 Map 에 저장 합 니 다.
시간 복잡 도: O (n)???????검색 대상 의 키 시간 은 O (1) 입 니까??
공간 복잡 도: O (n)????대상 을 만 드 는 데 필요 한 공간
3）
2), 2) 는 배열 을 옮 겨 다 니 며 대상 이나 맵 을 구축 하 는 것 이다.여기 서 먼저 배열 을 옮 겨 다 니 며 구축 대상 이나 맵 을 구축 한 다음 에 배열 을 옮 겨 다 니 며 목표 요 소 를 찾 을 수 있 습 니 다.(코드 자체 작성)
4 코드

/**

 * @param {number[]} nums

 * @param {number} target

 * @return {number[]}

 *  twoSum     

 */

  var twoSum = function(nums, target) {

    if(nums === null || nums.length <= 1){ //         1 

        return [];

    }

    //console.time("11");

    for(let i = 0; i < nums.length; i++){  //    2 

        let value = target - nums[i]; //   ，              

        for(let j = i + 1; j < nums.length; j++){

            if(value === nums[j]){

                //console.timeEnd("11"); //0.332ms

                return [i, j];//    ，       

            }

        }

    }

    return [];//    ，     

  };

  

  /**

 * @param {number[]} arr

 * @param {number} target

 * @return {number[]}

 *  twoSum    ，               ,,,    ，          ，      ，    

 */

  var twoSum_2 = function(arr, target) {

    if(arr === null || arr.length <= 1){ //         1 

        return [];

    }

    //console.time("22");

    arr.sort(function (a,b) {

        return a - b; //    ，    ，   

    });

    //   ，      twoSum

    let left = 0;

    let right = arr.length - 1;

    while(left < right){  //    ，    ，       

        if(arr[left] + arr[right] === target){

            //console.timeEnd("22");//0.413ms

            return [left, right];

        }else if(arr[left] + arr[right] > target){

            right--;

        }else {

            left++;

        }

    }

    return []; //        ，     

  };

  

  /**

 * @param {number[]} arr

 * @param {number} target

 * @return {number[]}

 *       twoSum           obj  ，   ，       

 */

  var twoSum_3 = function(arr, target) {

    if(arr === null || arr.length <= 1){ //         1 

        return [];

    }

    //console.time("22");

    let obj = {}; //     ,        。      （       ，         ），         

    for(let i = 0; i < arr.length; i++){

        let diff = target - arr[i]; //  

        if(obj[diff] || obj[diff] === 0){  //          obj.hasOwnProperty(diff)  obj[diff] !== undefined

            //console.timeEnd("2obj[diff] !== undefined2");//22: 0.341ms

            return [obj[diff], i];

        }

        obj[arr[i]] = i;//      （       ，         ），         ,  0,1,2...

    }

    return []; //        ，     

  };

  

  /**

 * @param {number[]} arr

 * @param {number} target

 * @return {number[]}

 *       twoSum   Map     

 */

  var twoSum_4 = function(arr, target) {

    if(arr === null || arr.length <= 1){ //         1 

        return [];

    }

    //console.time("22");

    let map = new Map(); //

    for(let i = 0; i < arr.length; i++){

        let diff = target - arr[i]; //  

        if(map.has(diff)){  //

            //console.timeEnd("2obj[diff] !== undefined2");//22: 0.341ms

            return [map.get(diff), i];

        }

        map.set(arr[i], i);//      （       ，         ），         ,  0,1,2...

    }

    return []; //        ，     

  };

  

  let nums = [3,2,4];

  let target = 6;

  console.log(twoSum(nums, target));

  console.log(twoSum_4(nums, target));

참고: 버클
백 리 는 2020 년 5 월 23 일
만약 잘못 이 있다 면 지적 해 주 십시오!권리 침해 가 있 으 면 연락 해서 삭제 해 주세요!