4 sum

概述FROM： https://leetcode.com/problems/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 give

FROM：https://leetcode.com/problems/4sum/

Given an arraySofnintegers,are there elementsa,b,c,anddinSsuch thata+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,-1,-2,2],and target = 0.A solution set is:[  [-1,1],[-2,1,2]]

最简单直观的办法就是四层循环，依次相加，找出符合条件的四元数组即可，时间复杂度为N＊N ＊ N ＊ N;

当然有更快的算法；

先考虑找出相加等于给定数字的二元数组的办法：

1. 将数组排序；

2. 两个指针， i & j， 分别从头和尾开始移动， 只考虑最简单的情况：

a) nums(i) + nums(j) > target; 因为已经排序， 所以有nums(i) + nums(j - 1) < nums(i) + nums(j)， 所以将指针j向前移动1为， 有可能得到和target相等的数字；

b) nums(i) + nums(j) < target; 相应的将i向后移动1位；

c) nums(i) + nums(j) == target; 这时已经找到一组复合条件的数字，分别将i 和j移动一位；

通过以上的步骤可以O（N）的时间内解决2 sum的问题；

然后考虑找出相加等于给定数字的三元组的问题：

1. 排序；

2. 从前（或者从后）开始，依次处理每个数字；

3. 从给定数字后面（或者前面）的子数组中， 寻找相加等于target － nums(i)的二元组；

4. 将第三步得到的二元组加上nums（i）扩充为3元组；

那么四元组和三元组的解法是一致的， 先找到三元组， 然后扩充为四元组；

package mainimport (	"fmt"	"sort")func main() {	nums := []int{1,2}	result := fourSum(nums,0)	for _,x := range result {		fmt.Printf("%v\n",x)	}}func fourSum(nums []int,target int) [][]int {	sort.Ints(nums)	result := make([][]int,10)	for i := len(nums) - 1; i > 2; i-- {		if i < len(nums)-1 && nums[i] == nums[i+1] {			continue		}		xs := threeSum(nums[:i],target-nums[i])		for _,x := range xs {			result = append(result,append(x,nums[i]))		}	}	return result}func threeSum(nums []int,target int) [][]int {	result := make([][]int,10)	for i := len(nums) - 1; i > 1; i-- {		if i < len(nums)-1 && nums[i] == nums[i+1] {			continue		}		xs := twoSum(nums[:i],nums[i]))		}	}	return result}func twoSum(nums []int,10)	for i,j := 0,len(nums)-1; i < j; {		if i > 0 && nums[i] == nums[i-1] {			i++			continue		}		if j < len(nums)-1 && nums[j] == nums[j+1] {			j--			continue		}		sum := nums[i] + nums[j]		if sum < target {			i++		} else if sum > target {			j--		} else {			result = append(result,[]int{nums[i],nums[j]})			i++			j--		}	}	return result}

总结

以上是内存溢出为你收集整理的4 sum全部内容，希望文章能够帮你解决4 sum所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。