一、数组

1. https://leetcode-cn.com/problems/two-sum/

时间复杂度：0(n²)

var twoSum = function (nums, target) {
  if (nums.length < 1) return false;
  for (let i = 0; i < nums.length - 1; i++) {
      for(let j = i+1; j < nums.length; j++){
          if(nums[i] + nums[j] === target){
              return [j,i]
          }
      }
  }
};

优化：时间复杂度：0(n)

var twoSum = function(nums, target) {
    const map = new Map()
    for(let i = 0; i < nums.length; i+=1){
        const n = nums[i]
        let n2 = target - n
        if(map.has(n2)){
            return [map.get(n2),i]
        }else{
            map.set(n,i)
        }
    }
};

2. https://leetcode-cn.com/problems/move-zeroes/

时间复杂度：0(n)
思路：利用快慢指针进行位置交换

var moveZeroes = function(nums) {
    let j = 0;
    for(let i = 0; i < nums.length; i++){
        if(nums[i] !== 0){
            if(i!==j){
                [nums[j],nums[i]] = [nums[i],nums[j]]
            }
            j++
        }
    }
    return nums
};

时间复杂度：0(n)
思路：将所有非0移入前面，在后面补0

var moveZeroes = function(nums) {
    let j = 0
    for(let i = 0; i < nums.length; i++){
        if(nums[i]!==0){
            nums[j] = nums[i]
            if(i!=j){
                nums[i] = 0
            }
            j++
        }
    }
    return nums
};

3. https://leetcode-cn.com/problems/container-with-most-water/submissions/

时间复杂度：0(n)
思路：枚举 left，right，(right-left) * height。
双指针，左右边界向中间收敛，确定一个最左边位置和一个最右边位置，判断左右两边的height哪个小向中间移动哪个。计算出最大的那个面积。

var maxArea = function(height) {
    let max = 0;
    let j = height.length - 1
    let i = 0
    while(i<j){
        let minHeight = height[i] < height[j] ? height[i++] : height[j--]
        let area = (j-i+1) * minHeight
        max = Math.max(max,area)
    }
    return max
};

4. https://leetcode-cn.com/problems/climbing-stairs/

时间复杂度：0(n)
思路：爬第三阶台阶可以从第一阶台阶跨两步走上去，也可以从第二阶台阶跨一步走上去。f(3) = f(2) + f(1)
同理上第n阶台阶f(n) = f(n-1) + f(n-2)

var climbStairs = function(n) {
    let f1 = 1,f2 = 2,f3 = 3
    if( n < 3 ) return n
    for(let i = 3; i <= n; i++){
        f3 = f1 + f2
          // 维护f1和f2
        f1 = f2
        f2 = f3
    }
     return f3
};

5. https://leetcode-cn.com/problems/3sum/

时间复杂度：0(n²)
思路：两边向中夹，首先进行从小到大排序，首先确定k和i的位置在最左边，j的位置在最右边，如果相加的和大于0，则右边向左边移动，反之。确定好每一步的去重操作。

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    let res = []
    if(nums && nums.length < 3) return res
    nums.sort((a,b) => a-b)
    for(let k = 0 ;k < nums.length-2; k++){
        if(nums[k] > 0) break; // 如果当前数字大于0，则三数之和一定大于0，所以结束循环
        if(k > 0 && nums[k] == nums[k-1]) continue; // 去重
        let i = k + 1;
        let j = nums.length - 1
        while(i < j){
            let sum = nums[k] + nums[i] + nums[j]
            if(sum < 0){
                i++
            }else if(sum > 0){
                j--
            }else{
                res.push([nums[k],nums[i],nums[j]])
                while(i<j && nums[i] === nums[++i]);
                while(i<j && nums[j] === nums[--j]);
            }
        }
    }
    return res
};

6. https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/

时间复杂度：0(n)
思路：快慢指针，当nums[i] !== nums[j]，把nums[j]的值放到nums[i+1]

var removeDuplicates = function(nums) {
    let i = 0;
    for(let j = 1; j< nums.length; j++){
        if(nums[i] !== nums[j]){
            i++
            nums[i] = nums[j]
        }
    }
    return i+1
};

7. https://leetcode-cn.com/problems/rotate-array/

时间复杂度：0(n)
思路：首先进行整个翻转，从第k个元素切割，左右两边各自翻转

function reverse (nums,start,end){
    while(end > start){
        [nums[start++],nums[end--]] = [nums[end],nums[start]]
    }
}
var rotate = function(nums, k) {
    if(nums.length < 2) return nums
    k %= nums.length
    reverse(nums, 0, nums.length - 1);
    reverse(nums, 0, k - 1);
    reverse(nums, k, nums.length - 1);
    return nums
};

8. https://leetcode-cn.com/problems/merge-sorted-array/

双指针时间复杂度：0(n)

const merge = function (nums1, m, nums2, n) {
  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--
    }
  }
  while (j >= 0) {
    nums1[k] = nums2[j]
    k--
    j--
  }
  return nums1
};

var merge = function(nums1, m, nums2, n) {
    nums1.splice(m)
    nums2.splice(n)
    nums1.push(...nums2)
    nums1.sort((a,b)=>a-b)
};

9. https://leetcode-cn.com/problems/plus-one/

时间复杂度：0(n)
思路：倒序循环，每次循环都进行对10取余操作，如果不等于0说明不大于10，直接返回，否则等于10，前面补1。

var plusOne = function(digits) {
    const len = digits.length;
    for(let i = len - 1; i >= 0; i--) {
        digits[i]++;
        digits[i] %= 10;
        if(digits[i]!=0)
            return digits;
    }
    digits = [1,...digits]
    digits[0] = 1;
    return digits;
};

10. https://leetcode-cn.com/problems/intersection-of-two-arrays-ii/

为两个数组分别建立 map，用来存储 num -> count 的键值对，统计每个数字出现的数量。
然后对其中一个 map 进行遍历，查看这个数字在两个数组中分别出现的数量，取出现的最小的那个数量（比如数组 1 中出现了 1 次，数组 2 中出现了 2 次，那么交集应该取 1 次），push 到结果数组中即可。

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersect = function (nums1, nums2) {
    const map1 = makCountMap(nums1)
    const map2 = makCountMap(nums2)
    const res = []
    for (let num of map1.keys()) {
        const count1 = map1.get(num)
        const count2 = map2.get(num)
        if (count2) {
            const pushCount = Math.min(count1, count2)
            for (let i = 0; i < pushCount; i++) {
                res.push(num)
            }
        }
    }
    return res
};
function makCountMap(nums) {
    let map = new Map()
    for (let i = 0; i < nums.length; i++) {
        let num = nums[i]
        let count = map.get(num)
        if (count) {
            map.set(num, count + 1)
        } else {
            map.set(num, 1)
        }
    }
    return map;
}