leetcode's Introduction

leetcode

No.	Title	Solution	Acceptance	Difficulty
0001	Two Sum	Go	50.1%	Easy
0015	3Sum	Go	32.8%	Medium
0018	4Sum	Go	36.5%	Medium
0021	Merge Two Sorted Lists	Go	62.8%	Easy
0080	Remove Duplicates from Sorted Array II	Go	53.6%	Medium
0088	Merge Sorted Array	Go	47.23%	Easy
0096	Unique Binary Search Trees	Go	59.9%	Medium
0167	Two Sum II - Input Array Is Sorted	Go	60.0%	Medium
0169	Majority Element	Go	46.0%	Medium
0274	H-Index	Go	38.4%	Medium
0380	Insert Delete GetRandom O(1)	Go	52.8%	Medium

解法公式

nSum 解法

設定終止條件，當 n < 2，代表沒有元素可以遍歷，返回 res。
如果 n = 2，我們可以使用 Tow Pointer 的方式來解決。
如果 n > 2，在每次迴圈中找出 target - 當前元素，之後使用遞迴的方式執行 nSum(nums, n - 1, i + 1, target)，直到 n = 2 的時候，找回符合的元素。

import "sort"

func Sum(nums []int, target int) [][]int {
	sort.Ints(nums)
	return nSum(nums, 4, 0, target)
}

func nSum(nums []int, n int, start int, target int) [][]int {
	length := len(nums)
	var res [][]int

	if n < 2 || length < n {
		return res
	}

	if n == 2 {
		small, big := start, length-1
		for small < big {
			left, right := nums[small], nums[big]
			sum := left + right

			if sum == target {
				res = append(res, []int{left, right})
				for small < big && nums[small] == left {
					small++
				}
				for small < big && nums[big] == right {
					big--
				}
			} else if sum > target {
				for small < big && nums[big] == right {
					big--
				}
			} else if sum < target {
				for small < big && nums[small] == left {
					small++
				}
			}
		}
	} else {
		i := start
		for i < length {
			now := nums[i]
			sub := nSum(nums, n-1, i+1, target-now)
			for _, s := range sub {
				s = append(s, now)
				res = append(res, s)
			}
			for i < length && nums[i] == now {
				i++
			}
		}
	}

	return res
}

Recommend Projects