TwoSum 及其变种

2sum问题

两数之和无疑是leetcode最基础的问题之一，不知是多少同学的入门题。
但两数之和其实也有多种玩法。

1.map法

for循环法我就不写了，map法就是将当前数的下标与要找的数放入map，当值出现时即可直接返回。
如： nums:[2,6,7,8,11] target:10
首先我们要将 target - nums[i] 和 i 放入map，i为数组下标
如 i = 0 时，nums[i] = 2，那此时要将 key=8,value=2 放入map，直到找到对应目标。

func twoSum(nums []int, target int) []int {
	dict := map[int]int{}
	for i, v := range nums {
		if _, exist := dict[v]; exist {
			return []int{dict[v], i}
		}
		dict[target - v] = i
	}
	return nil
}

可见，此方法下时间复杂度为 $O(n)$ 空间复杂度为 $O(n)$

当然，除此外还有一种更有趣的办法。

2.双指针法

通常来说，map法就足够了，但双指针法的思想很值得学习，而且下面也会用到。
由先，双指针法顾名思义，就是由左右两个指针，逐个查询，直至找到答案。

但双指针法有个前题，就是排好了序，所以在处理前要先排序。
通过左右指针，逐渐向中间靠拢，直至找到结果。

import "sort"

func twoSum(nums []int, target int) []int {
	sort.Ints(nums)
	left, right := 0, len(nums) - 1
	for left < right {
		if nums[left] + nums[right] < target {
			left++
		} else if nums[left] + nums[right] > target {
			right--
		} else {
			return []int{left,right}
		}
	}
	return nil
}

显然，由于需要排序，所以该方案的时间复杂度为$O(n^2\log(n))$ ，空间复杂度为 $O(1)$

显然这种解法和map法的差距很大，那为什么还要提这种方法呢？往下看吧

二、TwoSum $II$

在原有两数相加的基础上，有部分不同。原有两数相加有且仅有一个解，且无重复数字。
而本题有给的 nums 保住重复数字，且需要返回多种解。
如：nums=[5,3,1,3,2,6,2,8,4,5] target=10
那返回应为 [[5,5],[4,6],[2,8]]

如要上一道题只会用map法，那到本题就会没有思路，但如果上题已经了解了双指针法，那本题就会豁然开朗。

其实与上题双指针法只有两个不同，一就是如果有重复则跳过，二是如果有重复数还要确定是否相加也是结果。

所以只需要在上题的双指针法上做些修改

import "sort"

func twoSum(nums []int, target int) []int {
	sort.Ints(nums)
	ret := [][]int{}
	left, right := 0, len(nums) - 1
	for left < right {
		if nums[left] + nums[right] < target {
			left++
		} else if nums[left] + nums[right] > target {
			right--
		} else {
			ret = append(ret, []int{left,right})
			lv := nums[left]
			rv := nums[right]
			for nums[left] == lv && left < right {
				left++
			}
			for nums[right] == rv && left < right {
				right--
			}
		}
	}
	return ret
}

在很多时候多看一些解题思路，多了解其变化，对解题的思维会有很大提升。