【Day 19 】2021-05-28 - 两数之和
题目描述
入选理由
- 感受下什么是 hashtable
题目描述
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。加餐
我的回答
解法一
时空复杂度
时间复杂度：O(n)
空间复杂度: O(n)
var twoSum = function (nums, target) {
let map = new Map()
for (let i = 0; i < nums.length; i++) {
const cur = target - nums[i]
if (map.has(cur)) {
const index = map.get(cur)
return [i, index]
}
map.set(nums[i], i)
}
return result
};三数之和
时间复杂度：O(n^2)
空间复杂度: O(n)
const findTwoSum = (nums, start, k) => {
let map = {}
let result = []
let left = start
let right = nums.length - 1
while (left < right) {
const sum = nums[left] + nums[right]
if (sum === k) {
result.push([nums[left], nums[right]])
}
if (sum >= k) {
while (nums[right] === nums[right - 1]) {
right--
}
right--
}
if (sum <= k) {
while (nums[left] === nums[left + 1]) {
left++
}
left++
}
}
return result
}
var threeSum = function (nums) {
nums.sort((a, b) => a - b)
let result = []
let curr = 0
while (curr < nums.length) {
const twoSum = findTwoSum(nums, curr + 1, 0 - nums[curr])
if (twoSum.length) twoSum.forEach(v => result.push([nums[curr], ...v]))
while (nums[curr] === nums[curr + 1]) curr++
curr++
}
return result
};