LeetCode热题100（JavaScript）
哈希
两数之和
暴力解法
/*** @param {number[]} nums* @param {number} target* @return {number[]}*/
var twoSum = function(nums, target) {for(let i =0;i<nums.length;i++){let x1 = nums[i]for(let j = 0 ; j<nums.length;j++){if(i!=j){let x2 = nums[j]if(x1+x2==target){return [i,j]}}}}
};Map法
var twoSum = function(nums, target) {const map = new Map()for(let i=0;i<nums.length;i++){let key = target-nums[i]if(map.has(key)){return [map.get(key),i]}else{map.set(nums[i],i)} }return []
};字母异味词分组
/*** @param {string[]} strs* @return {string[][]}*/
var groupAnagrams = function(strs) {let map = new Map(); for (let i = 0; i < strs.length; i++) { let word = strs[i]; // 使用数组的 sort 方法对字符串的字符进行排序，并将排序后的字符数组重新连接成字符串 let sorted_word = word.split('').sort().join(''); if (map.has(sorted_word)) { map.get(sorted_word).push(word); } else { map.set(sorted_word, [word]); } } // 将Map中的值（数组）转换为数组返回 return [...map.values()];
};最长连续序列
var longestConsecutive = function(nums) {if (nums.length === 0) return 0; let set = new Set(nums); let maxSize = 0; for (let num of set) { // 跳过非连续序列的起始数字（即那些前面有数字的数字） if (!set.has(num - 1)) { let currentNum = num; let currentLength = 1; // 遍历连续序列 while (set.has(currentNum + 1)) { currentNum++; currentLength++; } // 更新最大长度 maxSize = Math.max(maxSize, currentLength); } } return maxSize;
};双指针
移动零
解法1
先遍历数组，计算非零元素的数量。然后，在第二次遍历中，只将非零元素复制回数组的前部，并跳过0。
function moveZeroes(nums) { let count = 0; for (let num of nums) { if (num !== 0) { count++; } } let writeIndex = 0; for (let num of nums) { if (num !== 0) { nums[writeIndex++] = num; } } // 填充剩余的0for (let i = writeIndex; i < nums.length; i++) { nums[i] = 0; } return nums
} 解法2
- 初始化两个指针，
slow和fast，都指向数组的第一个元素。 - 遍历数组（
fast从头到尾），对于每个nums[fast]：- 如果
nums[fast]不为 0，则交换nums[slow]和nums[fast]，并将slow向后移动一位（slow++）。 - 如果
nums[fast]为 0，则只移动fast指针。
- 如果
- 遍历结束后，所有非零元素都已经被移动到了数组的前面，而后面的元素则自动成为了 0
var moveZeroes = function(nums) {let slow=0let fast = 0for(fast;fast<nums.length;fast++){if(nums[fast]!=0){let swap = nums[slow]nums[slow] = nums[fast]nums[fast] = swapslow++}}return nums
};盛最多水的容器
- 初始化左指针
left为 0，右指针right为height.length - 1。 - 进入循环，当
left < right时执行以下步骤：- 计算当前容器的面积
area = Math.min(height[left], height[right]) * (right - left)。 - 更新最大面积
maxArea（如果area大于maxArea）。 - 如果
height[left] < height[right]，则left++（移动左指针），否则right--（移动右指针）。
- 计算当前容器的面积
- 退出循环后，
maxArea就是所求的最大面积。
var maxArea = function(height) {let left = 0let right = height.length-1let max = 0while(left<right){let h1 = height[left]let h2 = height[right]let area = Math.min(h1, h2) * (right - left)max = Math.max(max, area); if (h1 > h2) { right--; } else { left++; } }return max
};三数之和
-
排序：首先对输入的数组
nums进行排序。这是为了之后能够使用双指针技术有效地查找匹配项。 -
初始化：定义结果数组
res来存储找到的三元组，以及定义指针i、left和right分别用于遍历数组和作为双指针。 -
遍历数组：使用外层循环遍历数组
nums，其中i是第一个数的索引。为了避免找到重复的三元组，如果当前元素与前一个元素相同，则跳过。 -
双指针查找：在内层循环中，使用
left和right两个指针，在i之后的元素中查找满足nums[i] + nums[left] + nums[right] == 0的另外两个数。left从i+1开始，right从数组末尾开始。 -
计算和并调整指针：计算当前三个数的和
sum。如果sum等于0，说明找到了一个满足条件的三元组，将其添加到结果数组中，并移动left和right指针，同时跳过所有相同的元素，以避免重复的三元组。如果sum小于0，说明和太小，需要增加，因此将left指针右移。如果sum大于0，说明和太大，需要减小，因此将right指针左移。 -
返回结果：当遍历完整个数组后，所有满足条件的三元组都已被添加到结果数组中，返回结果数组。
var threeSum = function(nums) {// 首先对数组进行排序 nums.sort((a, b) => a - b); const result = []; let n = nums.length; // 遍历数组（除了最后两个元素，因为需要至少两个元素与当前元素相加） for (let i = 0; i < n - 2; i++) { // 跳过所有与当前nums[i]相同的元素，以避免重复的三元组 if (i > 0 && nums[i] === nums[i - 1]) continue; let left = i + 1; let right = n - 1; // 使用双指针在nums[i]之后的元素中查找 while (left < right) { const sum = nums[i] + nums[left] + nums[right]; if (sum === 0) { // 找到一个和为0的三元组，添加到结果中 result.push([nums[i], nums[left], nums[right]]); // 移动左右指针，并跳过所有相同的元素 while (left < right && nums[left] === nums[left + 1]) left++; while (left < right && nums[right] === nums[right - 1]) right--; left++; right--; } else if (sum < 0) { // 和小于0，说明需要增加和的值，因此左指针右移 left++; } else { // 和大于0，说明需要减少和的值，因此右指针左移 right--; } } } return result;
};滑动窗口
无重复字符的最长字串
var lengthOfLongestSubstring = function(s) { let left = 0 let maxLength = 0 let map = new Map() for(let right=0;right<s.length;right++){ if(map.get(s[right])>=left){ left = map.get(s[right])+1 } map.set(s[right],right) maxLength = Math.max(maxLength,right-left+1) } return maxLength
};