https://leetcode-cn.com/problems/two-sum/solution/jsshi-yong-map-by-hen-ji-shi/
map hashmap
image.png

  1. function twoSum(nums: number[], target: number): number[] {
  2.    let numsMap= new Map()
  3.     for(let i =0,len = nums.length;i<len;i++){
  4.         let index = numsMap.get(target-nums[i])
  5.         if(index !== undefined){
  6.             return [index,i]
  7.         }
  8.         numsMap.set(nums[i],i)
  9.     }
  10. };

二分法

有序数组 无重复元素

  1. // （版本一）左闭右闭区间
  3. var search = function(nums, target) {
  4.     let l = 0, r = nums.length - 1;
  5.     // 区间 [l, r]
  6.     while(l <= r) {
  7.         let mid = (l + r) >> 1;
  8.         if(nums[mid] === target) return mid;
  9.         let isSmall = nums[mid] < target;
  10.         l = isSmall ? mid + 1 : l;
  11.         r = isSmall ? r : mid - 1;
  12.     }
  13.     return -1;
  14. };
  16. // （版本二）左闭右开区间
  18. var search = function(nums, target) {
  19.     let l = 0, r = nums.length;
  20.     // 区间 [l, r）
  21.     while(l < r) {
  22.         let mid = (l + r) >> 1;
  23.         if(nums[mid] === target) return mid;
  24.         let isSmall = nums[mid] < target;
  25.         l = isSmall ? mid + 1 : l;
  26.         // 所以 mid 不会被取到
  27.         r = isSmall ? r : mid;
  28.     }
  29.     return -1;
  30. };

备注 :

  • number >> 位数 位运算，向右移几位 这里为1，相当于抹去了最后一位
    • 3>>1 就是 11 => 1
    • 4>>1 就是 100 =>10 就是2
    • 方便取中位数 除以2 向下取整