Leetcode Array

1 两数之和

# 无脑暴力解 3848 ms (27.38%) 11.8 MB
def twoSum(self, nums, target):
	"""
	:type nums: List[int]
	:type target: int
	:rtype: List[int]
	"""
	for i in range(len(nums) - 1):
		for j in range(i+1, len(nums)):
			if nums[i] + nums[j] == target:
				return [i, j]

// 单循环  72 ms (89.73%)  34.8 MB(35.22%)
var twoSum = function(nums, target) {
	let m = new Map();
	for (let i = 0; i < nums.length; i++){
		let val = nums[i]
		if (m.has(target - val)){
			return [m.get(target - val), i]
		}else{
			m.set(val, i)
		}
	}
	return []
};

15 三数之和

// 192ms 92.33%  47.4mb  35.09%
var threeSum = function(nums){
	let res = []
	nums.sort((a, b) => a-b)
	for (let i = 0; i <= nums.length-3; i++){
		if (i > 0 && nums[i] === nums[i-1]) continue
		for (let j = i+1, k = nums.length-1; j < k;){
			if (nums[j] === nums[j-1] && nums[k+1] !== undefined && nums[k] === nums[k+1]){
				k--
				continue
			}

			if (nums[j] + nums[k] < -nums[i]){
				j++
			}else if(nums[j] + nums[k] > -nums[i]){
				k--
			}else{
				res.push([nums[i], nums[j], nums[k]])
				j++
				k--
			}
		} 
	}
	return res
}
nums = [-1, 0, 1, 2, -1, -4]
// console.log(threeSum(nums))
// nums = [0, 0, 0, 0]
// nums = [-2, 0,0,2,2]
// nums = [1, 1, -2]
// nums = [-4,-2,-2,-2,0,1,2,2,2,3,3,4,4,6,6]
// nums = [-4,-2,1,-5,-4,-4,4,-2,0,4,0,-2,3,1,-5,0]
// nums = [-1,-2,-3,4,1,3,0,3,-2,1,-2,2,-1,1,-5,4,-3]
console.log(threeSum(nums))

视频里的有一种解法老师用python写的，说他觉得这种比较自然，相比上面写的这种。但是我用js写的时候就觉得还是上面这种更好，因为python的那种是直接把结果存tuple里，然后扔到set里面，这样就去重了。我还才知道对于两个tuple，只要里面每个位置的元素是相等的那就是相等的！但是js里不能这么搞啊。所以还是得用上面这种办法，先排序，第二个for里面用两个指针分别从两头往中间走。然而这两个continue的判断才是耗时间的地方ORZ，折腾好久。

看了他的判断是写成下面这样，感觉这样更优雅

var threeSum = function(nums){
	let res = []
	nums.sort((a, b) => a-b)
	for (let i = 0; i <= nums.length-3; i++){
		if (i > 0 && nums[i] === nums[i-1]) continue
		for (let j = i+1, k = nums.length-1; j < k;){
			if (nums[j] + nums[k] < -nums[i]){
				j++
			}else if(nums[j] + nums[k] > -nums[i]){
				k--
			}else{
				res.push([nums[i], nums[j], nums[k]])
				while(j<k && nums[j] === nums[j+1]){
					j++
				}
				while(j<k && nums[k] === nums[k-1]){
					k--
				}
				j++
				k--
			}
		} 
	}
	return res
}