leetcode

目錄

No.	Title	Solution	Acceptance	Difficulty	Frequency
0001	Two Sum	Go	50.1%	Easy
0002	Add Two Numbers	Go, Java	45.5%	Medium
0011	Container With Most Water	Go, Java	57.1%	Medium
0012	Integer to Roman	Go, Java	67.7%	Medium
0013	Roman to Integer	Go, Java	64.0%	Easy
0014	Longest Common Prefix	Go, Java	44.8%	Easy
0015	3Sum	Go, Java	36.3%	Medium
0018	4Sum	Go	36.5%	Medium
0019	Remove Nth Node From End of List	Go, Java	48.2%	Medium
0020	Valid Parentheses	Go	41.9%	Easy
0021	Merge Two Sorted Lists	Go, Java	66.3%	Easy
0026	Remove Duplicates from Sorted Array	Go, Java	59.2%	Easy
0027	Remove Element	Go, Java	53.58%	Easy
0028	Find the Index of the First Occurrence in a String	Go, Java	44.4%	Easy
0036	Valid Sudoku	Go, Java	61.7%	Medium
0045	Jump Game II	Go, Java	41.1%	Medium
0048	Rotate Image	Go, Java	77.2%	Medium
0049	Group Anagrams	Go, Java	70.4%	Medium
0054	Spiral Matrix	Go, Java	53.0%	Medium
0055	Jump Game	Go, Java	39.1%	Medium
0058	Length of Last Word	Go, Java	55.3%	Easy
0071	Simplify Path	Go, Java	46.7%	Medium
0073	Set Matrix Zeroes	Go, Java	59.0%	Medium
0080	Remove Duplicates from Sorted Array II	Go, Java	53.6%	Medium
0088	Merge Sorted Array	Go, Java	47.23%	Easy
0092	Reverse Linked List II	Go, Java	49.1%	Medium
0096	Unique Binary Search Trees	Go	59.9%	Medium
0121	Best Time to Buy and Sell Stock	Go, Java	54.7%	Easy
0122	Best Time to Buy and Sell Stock II	Go, Java	68.7%	Medium
0123	Best Time to Buy and Sell Stock III	Go, Java	50.1%	Hard
0125	Valid Palindrome	Go, Java	50.0%	Easy
0128	Longest Consecutive Sequence	Go, Java	47.2%	Medium
0134	Gas Station	Go, Java	45.9%	Medium
0138	Copy List with Random Pointer	Go, Java	59.6%	Medium
0141	Linked List Cycle	Go, Java	52.0%	Easy
0150	Evaluate Reverse Polish Notation	Go, Java	54.1%	Medium
0151	Reverse Words in a String	Go, Java	49.7%	Medium
0155	Min Stack	Go, Java	55.9%	Medium
0167	Two Sum II - Input Array Is Sorted	Go, Java	60.0%	Medium
0169	Majority Element	Go, Java	46.0%	Medium
0188	Best Time to Buy and Sell Stock IV	Go, Java	45.8%	Hard
0189	Rotate Array	Go, Java	39.56%	Medium
0202	Happy Number	Go, Java	57.6%	Easy
0205	Isomorphic Strings	Go, Java	46.4%	Easy
0219	Contains Duplicate II	Go, Java	48.2%	Easy
0224	Basic Calculator	Go, Java	44.9%	Hard
0238	Product of Array Except Self	Go, Java	67.3%	Medium
0242	Valid Anagram	Go, Java	66.2%	Easy
0274	H-Index	Go, Java	38.4%	Medium
0289	Game of Life	Go, Java	71.0%	Medium
0290	Word Pattern	Go, Java	42.8%	Easy
0380	Insert Delete GetRandom O(1)	Go, Java	52.8%	Medium
0383	Ransom Note	Go, Java	63.9%	Easy
0392	Is Subsequence	Go, Java	48.2%	Easy

解法公式

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
}