双指针或哈希表

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]

法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]
输出：[]

思路

1. 先对数组排序，方便去重、定位；
2. 固定第一个数 a = nums[i]，然后用双指针在剩余区间找 b + c = -a；
3. 跳过重复元素（避免三元组重复）；

function threeSum(nums) {
  const res = [];
  const n = nums.length;
  nums.sort((a, b) => a - b); // 排序

  for (let i = 0; i < n - 2; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) continue; // 跳过重复 a

    let left = i + 1;
    let right = n - 1;

    while (left < right) {
      const sum = nums[i] + nums[left] + nums[right];

      if (sum === 0) {
        res.push([nums[i], nums[left], nums[right]]);
        // 跳过重复 b 和 c
        while (left < right && nums[left] === nums[left + 1]) left++;
        while (left < right && nums[right] === nums[right - 1]) right--;
        left++;
        right--;
      } else if (sum < 0) {
        left++; // 和太小，右移 left
      } else {
        right--; // 和太大，左移 right
      }
    }
  }

  return res;
}

时间复杂度：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

思路：双指针

• left 从左边走，right 从右边走；
• leftMax 是目前左边见过的最高柱子；
• rightMax 是右边见过的最高柱子；

关键判断：

• 如果左边更矮，就看左边：
  • 如果左边比 leftMax 小，那就能接水；
  • 否则更新 leftMax
• 否则看右边：
  • 如果右边比 rightMax 小，那就能接水；
  • 否则更新 rightMax

/**
 * 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:盛最多水的容器中等hot

题目描述

给你 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++
    }
  }
};

思路二：双指针

我们维护三个指针：

• p0：左边界，指向应该放 0 的位置
• p2：右边界，指向应该放 2 的位置
• i：当前扫描的指针

我们遍历数组：

• 如果 nums[i] == 0：把它换到 p0 的位置，然后 p0++，i++
• 如果 nums[i] == 2：把它换到 p2 的位置，然后 p2--，但 i 不动（因为换过来的元素还没看）
• 如果 nums[i] == 1：跳过，i++

var sortColors = function(nums) {
  let p0 = 0, p2 = nums.length - 1;
  let i = 0;

  while (i <= p2) {
    if (nums[i] === 0) {
      [nums[i], nums[p0]] = [nums[p0], nums[i]];
      p0++;
      i++;
    } else if (nums[i] === 2) {
      [nums[i], nums[p2]] = [nums[p2], nums[i]];
      p2--;
      // 不移动 i，继续检查换过来的值
    } else {
      i++;
    }
  }
};

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) => {
    if (b[1] !== a[1]) return b[1] - a[1];           // 频率降序
    return a[0].localeCompare(b[0]);                // 字典升序
  });
  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)

lc560. 和为 K 的子数组困难hot

题目描述

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

示例 1：

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

示例 2：

输入：nums = [1,2,3], k = 3
输出：2

思路解析：前缀和 + 哈希表统计

我们定义前缀和 preSum[i] 为 nums[0..i] 的累加和。

那么对于某个区间 nums[i..j]，它的和为 k，等价于：

preSum[j] - preSum[i - 1] === k
=> preSum[i - 1] === preSum[j] - k

所以我们只需要：

• 维护当前的前缀和 sum
• 统计之前出现过的所有 preSum 的频率（用哈希表）
• 每次检查：是否存在 sum - k，有就说明存在子数组以当前结尾，和为 k

function subarraySum(nums, k) {
  const map = new Map(); // 前缀和出现的次数
  map.set(0, 1); // 前缀和为 0 的初始情况
  let sum = 0;
  let count = 0;

  for (const num of nums) {
    sum += num;
    if (map.has(sum - k)) {
      count += map.get(sum - k);
    }
    map.set(sum, (map.get(sum) || 0) + 1);
  }

  return count;
}

时间复杂度：O(n)

空间复杂度：O(n)（最坏情况下所有前缀和都不一样）

字符串压缩middlehot

题目描述

给定一组字符,使用原地算法将其压缩。压 缩后的长度必须始终小于或等于原数组长 度。数组的每个元素应该是长度为1的字符 (不是int整数类型)。在完成原地修改输 入数组后,返回数组的新长度。

示例1:

输入: chars=["a","a","b","b","c","c","c","c"]

输出:返回6

输入数组的前6个字符应该 是:["a","2","b","2","c","3"]

解释:"aa"被"a2"替代,"bb"被"b2"替 代,"ccc"被"c3"替代。

思路

使用两个指针：

• read 指针遍历原数组
• write 指针指向写入位置

遍历过程中统计连续相同字符的长度 count，写入字符和数字。

function compress(chars) {
  let write = 0;  // 写入指针
  let read = 0;   // 读取指针

  while (read < chars.length) {
    let char = chars[read];
    let count = 0;

    // 统计连续字符数
    while (read < chars.length && chars[read] === char) {
      read++;
      count++;
    }

    // 写入字符
    chars[write++] = char;

    // 写入数字（如果count > 1）
    if (count > 1) {
      let countStr = count.toString();
      for (let c of countStr) {
        chars[write++] = c;
      }
    }
  }

  // 返回写入指针，即新长度
  return write;
}

时间复杂度：O(n)，只遍历一次

空间复杂度：O(1)，原地修改