4 sum

前端之家收集整理的这篇文章主要介绍了4 sum前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

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 main

import (
	"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
}
原文链接:https://www.f2er.com/go/189587.html

猜你在找的Go相关文章