https://leetcode-cn.com/leetbook/detail/top-interview-questions-easy/ (opens new window)

两数之和

https://leetcode-cn.com/problems/two-sum/ (opens new window)

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
  const length = nums.length;
  let diffs = {};
  for (let i = 0; i < length; i++) {
    if (diffs[target - nums[i]] !== undefined) {
      return [diffs[target - nums[i]], i];
    } else {
      diffs[nums[i]] = i;
    }
  }
};

合并两个有序数组

https://leetcode-cn.com/problems/merge-sorted-array/ (opens new window)

/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
const merge = function (nums1, m, nums2, n) {
  // 初始化两个指针的指向，初始化 nums1 尾部索引k
  let i = m - 1,
    j = n - 1,
    k = m + n - 1;
  // 当两个数组都没遍历完时，指针同步移动
  while (i >= 0 && j >= 0) {
    // 取较大的值，从末尾往前填补
    if (nums1[i] >= nums2[j]) {
      nums1[k] = nums1[i];
      i--;
      k--;
    } else {
      nums1[k] = nums2[j];
      j--;
      k--;
    }
  }

  // nums2 留下的情况，特殊处理一下
  while (j >= 0) {
    nums1[k] = nums2[j];
    k--;
    j--;
  }
};

两个数组的交集

https://leetcode-cn.com/problems/intersection-of-two-arrays/ (opens new window)

// 笨方法
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function (nums1, nums2) {
  return [...new Set(nums1.filter((item) => nums2.includes(item)))];
};

// 排序+双指针
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function (nums1, nums2) {
  nums1.sort((a, b) => a - b);
  nums2.sort((a, b) => a - b);
  let i = 0;
  let j = 0;
  const result = [];
  while (i < nums1.length && j < nums2.length) {
    const num1 = nums1[i];
    const num2 = nums2[j];
    if (num1 === num2) {
      if (result[result.length - 1] !== num1 || !result.length) {
        result.push(num1);
      }
      i++;
      j++;
    } else if (num1 < num2) {
      i++;
    } else {
      j++;
    }
  }
  return result;
};
// hashmap
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function (nums1, nums2) {
  if (nums1.length > nums2.length) {
    return intersection(nums2, nums1);
  }
  const nums1Set = new Set(nums1);
  const nums2Set = new Set(nums2);
  const result = new Set();
  for (let num of nums1Set) {
    if (nums2Set.has(num)) {
      result.add(num);
    }
  }
  return [...result];
};

两个数组之间的交集 2

https://leetcode-cn.com/problems/intersection-of-two-arrays-ii/ (opens new window)

// 直接用双指针，比较好理解
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersect = function (nums1, nums2) {
  const result = [];
  nums1.sort((a, b) => a - b);
  nums2.sort((a, b) => a - b);
  let i = 0;
  let j = 0;
  while (i < nums1.length && j < nums2.length) {
    if (nums1[i] === nums2[j]) {
      result.push(nums1[i]);
      i++;
      j++;
    } else if (nums1[i] < nums2[j]) {
      i++;
    } else {
      j++;
    }
  }
  return result;
};

删除有序数组的重复项

https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/ (opens new window)

if ([0, 1].includes(nums.length)) {
  return nums.length;
}
let slow = 0;
let fast = 1;
const length = nums.length;
while (fast < length) {
  if (nums[slow] !== nums[fast]) {
    // 走到不相等的时候，slow走一步，是为了保留一个相同的值，剩下的重新赋值
    nums[++slow] = nums[fast];
  }
  // 如果相等，fast一直走
  fast++;
}
return slow + 1;

只出现一次的数字

https://leetcode-cn.com/problems/single-number/ (opens new window)

// 除了某个元素只出现一次以外，其余每个元素均出现两次 这句话是突破口

const singleNumber = (nums) => {
  let ans = 0;
  for (const num of nums) {
    // 异或运算
    ans = ans ^ num;
  }
  return ans;
};

// console.log(singleNumber([2,2,1]))
console.log(singleNumber([4, 1, 2, 1, 2]));

判断数组中是否有重复项

https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x248f5/ (opens new window)

const containsDuplicate1 = (nums) => {
  const cacheMap = {};

  for (const num of nums) {
    if (cacheMap[num]) {
      delete cacheMap[num];
    } else {
      cacheMap[num] = 1;
    }
  }

  return Object.keys(cacheMap).length < nums.length;
};

const containsDuplicate2 = (nums) => {
  nums.sort((a, b) => a - b);
  const len = nums.length;
  let slow = 0;
  let fast = 1;
  while (fast < len) {
    if (nums[slow] !== nums[fast]) {
      slow++;
      fast++;
    } else {
      break;
    }
  }
  return fast !== len;
};

移动零

https://leetcode-cn.com/problems/move-zeroes/ (opens new window)

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function (nums) {
  let length = nums.length;
  let i = 0;
  let j = 0;
  while (j < length) {
    if (nums[j] !== 0) {
      [nums[i], nums[j]] = [nums[j], nums[i]];
      i++;
    }
    j++;
  }
  return nums;
};

二分查找

https://leetcode-cn.com/problems/binary-search/ (opens new window)

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function (nums, target) {
  let i = 0;
  let j = nums.length - 1;
  while (i <= j) {
    let middleIndex = Math.floor((i + j) / 2);
    let middleValue = nums[middleIndex];
    if (middleValue === target) {
      return middleIndex;
    } else if (middleValue < target) {
      i = middleIndex + 1;
    } else {
      j = middleIndex - 1;
    }
  }
  return -1;
};

搜索插入位置

https://leetcode-cn.com/problems/search-insert-position/ (opens new window)

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function (nums, target) {
  let i = 0;
  let j = nums.length - 1;
  let middleIndex = 0;
  while (i <= j) {
    middleIndex = Math.floor((i + j) / 2);
    let middleValue = nums[middleIndex];
    if (middleValue === target) {
      return middleIndex;
    } else if (middleValue < target) {
      i = middleIndex + 1;
    } else {
      j = middleIndex - 1;
    }
  }
  return i;
};

寻找数组的中心下标

https://leetcode-cn.com/problems/find-pivot-index/ (opens new window)

/**
 * @param {number[]} nums
 * @return {number}
 */
var pivotIndex = function (nums) {
  let total = nums.reduce((pre, cur) => pre + cur, 0);
  let sum = 0;
  for (let i = 0; i < nums.length; i++) {
    if (sum * 2 + nums[i] === total) {
      return i;
    } else {
      sum += nums[i];
    }
  }
  return -1;
};

斐波那切数列

const fib = (n) => {
  if (n === 0) {
    return 0;
  }
  if (n === 1 || n === 2) {
    return 1;
  }
  return fib(n - 1) + fib(n - 2);
};

LRU 最少使用

https://leetcode-cn.com/problems/OrIXps/ (opens new window)

运用所掌握的数据结构，设计和实现一个 LRU (Least Recently Used，最近最少使用) 缓存机制

/**
 * @param {number} capacity
 */
var LRUCache = function (capacity) {
  this.cache = new Map();
  this.capacity = capacity;
};

/**
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function (key) {
  if (this.cache.has(key)) {
    const value = this.cache.get(key);
    // 更新位置
    this.cache.delete(key);
    this.cache.set(key, value);

    return value;
  }

  return -1;
};

/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function (key, value) {
  // 已经存在的情况下，更新其位置到”最新“即可
  // 先删除，后插入
  if (this.cache.has(key)) {
    this.cache.delete(key);
  } else {
    // 插入数据前先判断，size是否符合capacity
    // 已经>=capacity，需要把最开始插入的数据删除掉
    // keys()方法得到一个可遍历对象,执行next()拿到一个形如{ value: 'xxx', done: false }的对象
    if (this.cache.size >= this.capacity) {
      this.cache.delete(this.cache.keys().next().value);
    }
  }

  this.cache.set(key, value);
};

const lRUCache = new LRUCache(2);

console.log(lRUCache.put(1, 1)); // 缓存是 {1=1}
console.log(lRUCache.put(2, 2)); // 缓存是 {1=1, 2=2}
console.log(lRUCache.get(1)); // 返回 1
console.log(lRUCache.put(3, 3)); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
console.log(lRUCache.get(2)); // 返回 -1 (未找到)
console.log(lRUCache.put(4, 4)); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
console.log(lRUCache.get(1)); // 返回 -1 (未找到)
console.log(lRUCache.get(3)); // 返回 3
console.log(lRUCache.get(4)); // 返回 4