06-Sum.md

Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1]. 

关键

• 假定只有一种组合符合要求

• 不能使用相同元素

解法一： 两个for循环

functwoSum(nums []int, targetint) []int { n:=len(nums) fori:=0; i<n; i++ { forj:=i+1; j<n; j++ { ifcheck:=nums[i]+nums[j]; check==target { return []int{i, j} } } } returnnil }

虽然可以AC，但该算法时间复杂度为O(n^2)，速度是比较慢的。

可以利用map类型巧妙优化，即利用map的key存值。

解法二：利用map类型

functwoSum(nums []int, targetint) []int { m, n:=make(map[int]int), len(nums) fori:=0; i<n; i++ { another:=target-nums[i] ifj, check:=m[another]; check { return []int{j, i} } m[nums[i]] =i } returnnil }

两个返回值的方式可以检查map是否存在目标键值对， 例如 value, check := m['test']，返回的value是键test对应的值， check是一个bool值，表示是否存在test对应的键值对。

优化后可以看到时间复杂度为O(n)。

3Sum

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:

 [ [-1, 0, 1], [-1, -1, 2] ]

关键

• must not contain duplicate triplets

• 根据例子，隐藏了一个条件，每个解法里的元素是从小到大排序。

方法一、暴力法

funcisExist(nums [][]int, aint, bint) bool { iflen(nums) >0 { fori:=len(nums)-1; i>=0; i-- { ifnums[i][0] ==a&&nums[i][1] ==b { returntrue } elseifnums[i][0] <a { returnfalse } } } returnfalse } functhreeSum(nums []int) [][]int { sort.Ints(nums) varsolutions [][]intn:=len(nums) fori:=0; i<n-2; i++ { forj:=i+1; j<n-1; j++ { fork:=j+1; k<n; k++ { ifnums[i] +nums[j] +nums[k] ==0 { ifflag:=isExist(solutions, nums[i], nums[j]); flag { continue } solutions=append(solutions, []int{nums[i], nums[j], nums[k]}) } } } } returnsolutions }

然而超时了。。。看来O(n^3)的时间复杂度是不可行的。

只能用两层循环找出三个元素，可以先控制第一个不变，后两个数的确定可以使用low/high pointer找出来。

functhreeSum(nums []int) [][]int { varsolutions [][]intn:=len(nums) sort.Ints(nums) fori:=0; i<n-2; i++ { j, k:=i+1, n-1forj<k { ifnums[i] +nums[j] +nums[k] ==0 { solutions=append(solutions, []int{nums[i], nums[j], nums[k]}) j++; k--; forj<k&&nums[j] ==nums[j-1] { j++ } forj<k&&nums[k] ==nums[k+1] { k-- } } elseifnums[i] +nums[j] +nums[k] <0 { j++ } else { k-- } } fori<n-2&&nums[i] ==nums[i+1] { i++ } } returnsolutions }

3Sum Closest

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

For example, given array S = {-1 2 1 -4}, and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

关键：

• Return the sum of the three integers.

• You may assume that each input would have exactly one solution.

• 和上一道类似

解法：

funcgetAbs(numint) int { ifnum>0 { returnnum } return-num } functhreeSumClosest(nums []int, targetint) int { sort.Ints(nums) varsolutionsint=nums[0]+nums[1]+nums[2] n, distance:=len(nums), getAbs(solutions-target) fori:=0; i<n; i++ { j, k:=i+1, n-1forj<k { val:=nums[i]+nums[j]+nums[k] ifval==target { returnval } else { temp:=getAbs(val-target) iftemp<distance { distance=tempsolutions=val } } ifval<target { j++ } else { k-- } } } returnsolutions }

4Sum

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note: The solution set must not contain duplicate quadruplets.

For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0. A solution set is:

 [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]

和前面类似

解法：

funcfourSum(nums []int, targetint) [][]int { varsolutions [][]intn:=len(nums) sort.Ints(nums) fori:=0; i<n-3; i++ { forj:=i+1; j<n-2; j++ { k, l:=j+1, n-1fork<l { sum:=nums[i]+nums[j]+nums[k]+nums[l] ifsum==target { solutions=append(solutions, []int{nums[i], nums[j], nums[k], nums[l]}) k++; l--; fork<l&&nums[k] ==nums[k-1] { k++ } fork<l&&nums[l] ==nums[l+1] { l-- } } elseifsum<target { k++ } else { l-- } } forj<n-2&&nums[j] ==nums[j+1] { j++ } } fori<n-3&&nums[i] ==nums[i+1] { i++ } } returnsolutions }