双指针或哈希表

lc88. 合并两个有序数组简单hot

题目描述：

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。

初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。

示例 1：

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]

示例 2：

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]

思路：

• 倒叙比较 如果nums2[len2] 比 nums1[len1]大的话，就放进nums1[len]处

• 反之则把nums1[len1]放进nums1[len]处

• 若len2'指针'先走完，则nums1为已经排序好的数组

  • 若len1'指针'先走完，则说明nums2[len2]以前的元素全都比nums1小，就把剩余的逐个放进nums1中即可

时间复杂度为O(m + n)

/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
var merge = function(nums1, m, nums2, n) {
  let len = m + n - 1
  let l2 = n - 1, l1 = m - 1
  while(l2 >= 0) {
    nums1[len--] = nums1[l1] >= nums2[l2] ? nums1[l1--] : nums2[l2--]
  }
};

另题解：

用js自带的sort方法

js 的sort方法时间复杂度为O(nlogn)

时间复杂度为 O(n+ (m + n)log(m + n))

var merge = function(nums1, m, nums2, n) {
    for(let i = 0; i < n; i++){ 
        nums1[i + m] = nums2[i] 
    } 
    nums1.sort((a, b) => a - b)
};

lc1. 两数之和简单hot

题目描述

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

示例：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1]

法1 暴力法

// 两层for循环暴力求解
// 时间复杂度O（n^2）
var twoSum = function(nums, target) {
    if(nums.length < 2) return false
    for(let i = 0; i < nums.length; i++) {
        const temp = target - nums[i]
        for(let j = i + 1; j < nums.length; j++) {
            if(temp === nums[j]) return [i, j]
            else continue
        }
    }
};

法2 利用数组查找

思路：

使用一层循环，把要找的第二个数命名为n，新增一个数组temp，并遍历nums数组，如果在temp数组下标为n中找不到，就把第一个数的位置存进数组里

// 时间复杂度On

var twoSum = function(nums, target) {
	const temp = []
	for(let i = 0; i < nums.length; i++) {
        const diff = target - nums[i]
		if(temp[diff] != undefined) {
			return [i, temp[diff]]
		} else {
			temp[nums[i]] = i
		}
	}
}

法3 同法2 利用js的map数据结构

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

lc15. 三数之和中等hot

题目描述

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

示例 2：

输入：nums = []
输出：[]
示例 3：

输入：nums = [0]
输出：[]

法一 模仿两数之和

可以模仿两数之和，先循环一遍将nums[i]当成两数之和的target，然后重复两数之和的操作

const threeSum = function(nums) {
    let map = new Map()
    let result = []
    for(let i = 0; i < nums.length - 2; i++) {
		// 第一个数
		let first = nums[i]
		for(let j = i+1; j < nums.length; j++) {
			// 第三个数
			let second = 0 - nums[j] - first
			if(map.has(second)) {
				result.push([first, second, nums[j]]) 
			}
			map.set(nums[j], j)
		}
		map.clear()
	}
	return result
}

// 测试
var nums = [-1, 0, 1, 2, -1, -4] 
threeSum(nums)
// [[-1,0,1],[-1,2,-1],[0,1,-1]] // 存在重复元组

因为通不过测试用例，就更谈不上击败执行用时和内存消耗了

在数组中去重元组会消耗更多的内存和时间，这种做法不推荐

法二 排序加双指针

思路：

• 先对数组元素进行排序，然后进行循环，把nums[i]和nums[i - 1]的元素去重，然后将first置为i，second置为i + 1，third置为数组的最后一位

• 然后三位数相加

• 如果sum === 0 那就推进result里面

• 判断重复情况

  • 如果数组中下标为second的值和second + 1的值相等 那么second往后走一位
  • 同理 如果数组中下标为third的值和third - 1的值相等 那么third往回走一位

• 如果 sum > 0 那就third往回走一位

• 如果 sum < 0 那就second往后走一位

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    if(!nums || nums.length < 3) return []

    let result = [], first, second, third
    nums.sort((a, b) => a - b)
    for(let i = 0; i < nums.length - 2; i++) {
        // 因为数组为升序 假如这个first都小于0 那肯定整体加起来肯定大于0
        if(nums[i] > 0) break

        // 去重
        while(i > 0 && nums[i] === nums[i - 1]) i++

        // 第一个数
        first = i
        // 第二个数
        second = i + 1
        // 第三个数
        third = nums.length - 1

        while(second < third) {
            const sum = nums[first] + nums[second] + nums[third]
            if(sum === 0) {
                result.push([nums[first], nums[second], nums[third]])
                // 去重
                while(second < third && nums[second] === nums[second + 1]) second++
                while(second < third && nums[third] === nums[third - 1]) third--

                second++
                third--
            } else if(sum > 0) third--
            else if(sum < 0) second++
        }
    }
    return result
};

时间复杂度：O(n^2)，数组排序 O(nlogn)，遍历数组 O(n)，双指针遍历 O(n)，总体 O(NlogN)+O(n) * O(n) 空间复杂度:O(1)

lc18. 四数之和中等

题目描述

给你一个由 n 个整数组成的数组nums，和一个目标值target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] ：

0 <= a, b, c, d < n a、b、c 和 d 互不相同 nums[a] + nums[b] + nums[c] + nums[d] == target 你可以按 任意顺序 返回答案

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：

输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

思路：

和三数之和类似，多套了一层

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function(nums, target) {
    nums.sort((a,b) => a - b)
    const result = []

    for (let i = 0;i < nums.length -3;i++) {
        // 去重
        while (i > 0 && nums[i] === nums[i-1]) i++

        for(j = i + 1;j < nums.length - 2; j++) {
            while (j > i + 1 && nums[j] === nums[j - 1])  j++

            let third = j + 1, fourth = nums.length - 1
            while(third < fourth) {
                const sum = nums[i] + nums[j] + nums[third] + nums[fourth]
                if (sum == target) {
                    result.push([nums[i], nums[j], nums[third], nums[fourth]])
                }
                if (sum <= target) {
                    // 如果头部指针等于后一个元素，则third一直往后移
                    while (nums[third] === nums[++third]);
                } else {
                    // 如果尾部指针等于前一个元素，则fourth一直往前移
                    while (nums[fourth] === nums[--fourth]);
                }
            }
        }
    }
    return result
};

lc165. 比较版本号中等hot

题目描述

给你两个版本号 version1 和 version2 ，请你比较它们。

版本号由一个或多个修订号组成，各修订号由一个 '.' 连接。每个修订号由 多位数字 组成，可能包含 前导零 。每个版本号至少包含一个字符。修订号从左到右编号，下标从 0 开始，最左边的修订号下标为 0，下一个修订号下标为 1 ，以此类推。例如，2.5.33 和 0.1 都是有效的版本号。

比较版本号时，请按从左到右的顺序依次比较它们的修订号。比较修订号时，只需比较 忽略任何前导零后的整数值 。也就是说，修订号 1 和修订号 001 相等 。如果版本号没有指定某个下标处的修订号，则该修订号视为 0 。例如，版本 1.0 小于版本 1.1 ，因为它们下标为 0 的修订号相同，而下标为 1 的修订号分别为 0 和 1 ，0 < 1 。

返回规则如下：

• 如果 version1 > version2 返回 1，
• 如果 version1 < version2 返回 -1，
• 除此之外返回 0。

示例 1：

输入：version1 = "1.01", version2 = "1.001"
输出：0
解释：忽略前导零，"01" 和 "001" 都表示相同的整数 "1"

示例 2：

输入：version1 = "1.0", version2 = "1.0.0"
输出：0
解释：version1 没有指定下标为 2 的修订号，即视为 "0"

示例 3：

输入：version1 = "0.1", version2 = "1.1"
输出：-1
解释：version1 中下标为 0 的修订号是 "0"，version2 中下标为 0 的修订号是 "1" 。0 < 1，所以 version1 < version2

var compareVersion = function(version1, version2) {
  let v1 = version1.split('.')
  let v2 = version2.split('.')
  while(v1.length || v2.length) {
    let count1 = +v1.shift() || 0
    let count2 = +v2.shift() || 0

    if(count1 > count2) {
      return 1
    } else if(count1 < count2) {
      return -1
    } else if(count1 === count2) {
      continue
    } else {
      return 0
    }
  }
  return 0
};

时间复杂度:O(n)

空间复杂度:O(n)

优化:双指针

var compareVersion = function(version1, version2) {

  let v1 = 0, v2 = 0
  while(v1 < version1.length || v2 < version2.length) {
    let a = ''
    for(; v1 < version1.length && version1[v1] !== '.'; v1++) {
      a += version1[v1]
    }
    v1++
    let b = ''
    for(; v2 < version2.length && version2[v2] !== '.'; v2++) {
      b += version2[v2]
    }
    v2++
    if(+a !== +b) return +a > +b ? 1 : -1
  }
  return 0
};

时间复杂度:O(n)

空间复杂度:O(1)

lc349. 两个数组的交集简单

题目描述

给定两个数组，编写一个函数来计算它们的交集。

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

示例 2：

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]

思路

这道题很简单就用hash

var intersection = function(nums1, nums2) {
  const map = new Map()
  const res = []
  for(let i = 0; i < nums1.length; i++) {
    if(!map.has(nums1[i])) map.set(nums1[i], 1)
  }
  for(let i = 0; i < nums2.length; i++) {
    if(map.has(nums2[i])) {
      res.push(nums2[i])
      map.delete(nums2[i])
    }
  }
  return res
};

时间复杂度O(m + n)

空间复杂度:O(m + n)

lc350. 两个数组的交集 II简单

题目描述

给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]

示例 2:

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]

思路：排序后双指针

var intersect = function(nums1, nums2) {
  nums1.sort((a, b) => a - b)
  nums2.sort((a, b) => a - b)
  let l1 = 0, l2 = 0
  const res = []
  while(l1 < nums1.length && l2 < nums2.length) {
    if(nums1[l1] === nums2[l2]) {
      res.push(nums1[l1])
      l1++
      l2++
    }
    if(nums1[l1] > nums2[l2]) l2++
    if(nums1[l1] < nums2[l2]) l1++
  }
  return res
};

时间复杂度:O(nlogn)

空间复杂度:O(nlogn)

lc611. 有效的三角形个数中等

题目描述

给定一个包含非负整数的数组，你的任务是统计其中可以组成三角形三条边的三元组个数。

示例 1:

输入: [2,2,3,4]
输出: 3

解释:
有效的组合是: 
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3

思路：

和上面的三数之和类似

首先明白三角形是两边之和大于第三边 两边之差小于第三边

如果数组是升序的 那么只用考虑两边之和

利用双指针

• 对数组进行升序排序

• 设置变量k从尾开始遍历

• 设置变量j为k - 1

• 设置变量i为0

• 判断nums[i] + nums[j]是否大于nums[k]的值

• 如果nums[i] + nums[j] > nums[k] 那么在i∈[i, j]中的值都满足 (不信自己试试看！)

  • 然后j往回走再试

• 如果nums[i] + nums[j] <= nums[k] 那么i往后走一个

• 返回count

/**
 * @param {number[]} nums
 * @return {number}
 */
var triangleNumber = function(nums) {
    if(!nums || nums.length < 3) return 0

    let count = 0
    nums.sort((a, b) => a - b)
    for(let k = nums.length - 1; k > 1; k--) {
        let i = 0
        let j = k - 1
        while(i < j) {
            if(nums[i] + nums[j] > nums[k]) {
                count += j - i
                j--
            } else {
                i++
            }
        }
    }
    return count
};

时间复杂度:O(n^2)，其中 n 是数组 nums 的长度。我们需要 O(nlogn) 的时间对数组 nums 进行排序，随后需要 O(n^2)的时间使用一重循环枚举 k 的下标以及使用双指针维护 i, j 的下标。

空间复杂度:O(logn)，即为排序需要的栈空间。

lc42. 接雨水困难hot

题目描述

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]

输出：6

解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 
表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 

示例 2：
输入：height = [4,2,0,3,2,5]

输出：9

思路：双指针

当左边最大挡板＜右边最大挡板，左边向前挺近，最终值加上当前左最大挡板-当前左指针所指值（相当于左边只要不超过右边，右边最大挡板稳定兜底，左边无脑挺近累加）

/**
 * max water
 * @param arr int整型一维数组 the array
 * @return long长整型
 */
function maxWater( arr ) {
    // write code here
    let left = 0, right = arr.length - 1
    let lmax = 0, rmax = 0, sum = 0
    while(left < right) {
        lmax = Math.max(lmax, arr[left])
        rmax = Math.max(rmax, arr[right])
        if(lmax < rmax) {
            sum += (lmax - arr[left])
            left++
        } else {
            sum += (rmax - arr[right])
            right--
        }
    }
    return sum
}

时间复杂度:O(n)

空间复杂度:O(1)

单调栈

var trap = function(height) {
  let ans = 0;
  const stack = [];
  const n = height.length;
  for (let i = 0; i < n; ++i) {
    while (stack.length && height[i] > height[stack[stack.length - 1]]) {
      const top = stack.pop();
      if (!stack.length) {
        break;
      }
      const left = stack[stack.length - 1];
      const currWidth = i - left - 1;
      const currHeight = Math.min(height[left], height[i]) - height[top];
      ans += currWidth * currHeight;
    }
    stack.push(i);
  }
  return ans;
};

时间复杂度:O(n)

空间复杂度:O(n)

lc11:盛最多水的容器中等

题目描述

给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器。

示例 1：

输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2：

输入：height = [1,1]
输出：1

示例 3：

输入：height = [4,3,2,1,4]
输出：16

示例 4：

输入：height = [1,2,1]
输出：2

思路

这道题远比上一道题简单，用一个简单的双指针就好了

var maxArea = function(height) {
  let left = 0, right = height.length - 1
  let sum = 0
  while(left < right) {
    let res = Math.min(height[left], height[right]) * (right - left)
    sum = Math.max(res, sum)
    height[left] > height[right] ? right-- : left++
  }
  return sum
};

时间复杂度:O(n)

空间复杂度:O(1)

lc75. 颜色分类中等

题目描述

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ， 原地 (opens new window) 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库的sort函数的情况下解决这个问题。

示例 1：

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

示例 2：

输入：nums = [2,0,1]
输出：[0,1,2]

思路一：暴力法

一次遍历，然后等于零的就unshift到最前面，等于2的就push到最后面

var sortColors = function(nums) {
  for(let i = 0; i < nums.length; ) {
    if(nums[i] === 0) {
      nums.unshift(nums.splice(i, 1))
      i++
    } else if(nums[i] === 2) {
      nums.push(nums.splice(i, 1))
    } else {
      i++
    }
  }
};

思路二：双指针

var sortColors = function(nums) {
    let l = 0, r = nums.length-1;
    let cur = 0;

    function swap(i,j){
        [nums[i],nums[j]] = [nums[j],nums[i]];
    }

    while(cur <= r){
        while(cur >= l && cur <= r && nums[cur] !== 1){
            if(nums[cur] === 0) swap(cur,l++);
            else if (nums[cur] === 2) swap(cur, r--);
        }
        cur++;
    }

    return nums;
};

lc128. 最长连续序列中等hot

题目描述

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1：

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2：

输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

利用set数据结构

var longestConsecutive = function(nums) {
  let maxCount = 0
  nums = new Set(nums)

  for(let value of nums) {
    // 因为是未排序的数组，所以从没有比他小1的数开始，保证他是连续序列的开始位
    if(nums.has(value - 1)) continue

    let count = 1
    while(nums.has(value + 1)) {
      nums.delete(value + 1) 
      count++
      value++
    }

    maxCount = Math.max(maxCount, count)
  }
  return maxCount
};

时间复杂度:O(n)

空间复杂度:O(1)

lc692. 前K个高频单词中等

题目描述

给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。

返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。

示例 1：

输入: words = ["i", "love", "leetcode", "i", "love", "coding"], k = 2
输出: ["i", "love"]
解析: "i" 和 "love" 为出现次数最多的两个单词，均为2次。
    注意，按字母顺序 "i" 在 "love" 之前。

示例 2：

输入: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
输出: ["the", "is", "sunny", "day"]
解析: "the", "is", "sunny" 和 "day" 是出现次数最多的四个单词，
    出现次数依次为 4, 3, 2 和 1 次。

var topKFrequent = function(words, k) {
  const map = new Map()
  for(let i = 0; i < words.length; i++) {
    map.set(words[i], map.has(words[i]) ? map.get(words[i]) + 1: 1)
  }

  const arr = Array.from(map)
  arr.sort((a, b) => b[1] - a[1] || +(a > b) || +(a === b) - 1)
  return arr.slice(0, k).map(item => item[0])
};

时间复杂度:O(n)

空间复杂度:O(n)

977. 有序数组的平方简单

题目描述

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例 1：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

示例 2：

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

思路

我们可以使用两个指针分别指向位置 0 和 n−1，每次比较两个指针对应的数，选择较大的那个逆序放入答案并移动指针。这种方法无需处理某一指针移动至边界的情况

var sortedSquares = function(nums) {
  const n = nums.length;
  const ans = new Array(n);
  for (let i = 0, j = n - 1, pos = n - 1; i <= j;) {
    if (nums[i] * nums[i] > nums[j] * nums[j]) {
      ans[pos] = nums[i] * nums[i];
      ++i;
    } else {
      ans[pos] = nums[j] * nums[j];
      --j;
    }
    --pos;
  }
  return ans;
};

时间复杂度:O(n)

空间复杂度:O(1)