Open yanyue404 opened 1 year ago
Leetcode 第一题 https://leetcode.cn/problems/two-sum
给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那两个整数,并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1:
输入:nums = [2, 3,7,11,15], target = 9 输出:[0,1] 解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。
示例 2:
输入:nums = [3,2,4], target = 6 输出:[1,2]
示例 3:
输入:nums = [3,3], target = 6 输出:[0,1]
提示:
// 暴力双循环 // 时间复杂度:O(n^2) // 空间复杂度:O(1) const twoSum = function (nums, target) { for (let m = 0; m < nums.length; m++) { for (let n = 0; n < nums.length; n++) { if (nums[m] + nums[n] === target) { return [m, n]; } } } };
// 一次循环 + indexOf // 时间复杂度:O(n^2) // 空间复杂度:O(1) var twoSum = function(nums, target) { var _result nums.some(function(item, index) { var _index = nums.indexOf(target - item) if (_index !== -1 && index !== _index) { _result = [index, _index] return true } }) return _result }
知识点:indexOf 的时间复杂度?https://juejin.cn/post/7031833133938901022
知识点:indexOf
// 一趟哈希表 // 时间复杂度:O(n) // 空间复杂度:O(n) var twoSum = function(nums, target) { const map = {} for (let i = 0; i < nums.length; i++) { const n = nums[i] if (target - n in map) { return [map[target - n], i] } else { map[n] = i } } }
// 使用 Map var twoSum = function (nums, target) { const map = new Map(); for (let i = 0; i < nums.length; i++) { const complement = target - nums[i]; if (map.has(complement)) { return [map.get(complement), i]; } map.set(nums[i], i); } };
// 排序 + 双指针 // 时间复杂度:O(n^2) // 空间复杂度:O(n) var twoSum = function(nums, target) { // Array.from 深拷贝一个新的排序后的数组 let arr = Array.from(nums).sort((a, b) => a - b) let i = 0, j = arr.length - 1 while (i < j) { if (arr[i] + arr[j] === target) { return [nums.indexOf(arr[i]), nums.lastIndexOf(arr[j])] } else if (arr[i] + arr[j] > target) { j-- } else { i++ } } }
知识点:如何 copy 一个数组?
数组 item 为基础类型时以下方法为深拷贝:
[...arr]
Array.from(arr)
arr.slice()
arr.concat()
arr.map(v=>v)
arr.filter(v=> true)
Object.assign([], arr)
// 二分法 // 0-500 内的一个数: target : 365 range: [0, 500] // 250 [251, 500] // 375 [251, 374] // 312 [313, 374] // 343 [344, 374] // 359 [360, 374] // 367 [360, 366] // 363 [364, 366] // 365 => 365
// 排序 + 二分法 // 时间复杂度:O(n^2) // 空间复杂度:O(n) const twoSum = function (nums, target) { // Array.from 深拷贝一个新的排序后的数组 const arr = Array.from(nums).sort((a, b) => a - b); let left = 0; let right = arr.length - 1; while (left < right) { let mid = Math.floor((right + left) / 2); if (arr[left] + arr[right] === target) { break; // 左半部分首尾和已经大于目标值,结果肯定在左半部分 } else if (arr[left] + arr[mid] > target) { right = mid; // 右半部分首尾和还是小于目标值,结果肯定在右半部分 } else if (arr[mid] + arr[right] < target) { left = mid; } else if (arr[left] + arr[right] < target) { left++; } else if (arr[left] + arr[right] > target) { right--; } } return [nums.indexOf(arr[left]), nums.lastIndexOf(arr[right])]; };
专题式学习计划
1. 两数之和
给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那两个整数,并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1:
示例 2:
示例 3:
提示:
解法 1:
解法 2:
知识点:indexOf
的时间复杂度?https://juejin.cn/post/7031833133938901022解法 3:
解法 4:
知识点:如何 copy 一个数组?
数组 item 为基础类型时以下方法为深拷贝:
[...arr]
Array.from(arr)
arr.slice()
arr.concat()
arr.map(v=>v)
arr.filter(v=> true)
Object.assign([], arr)
解法 5: