Skip to content

POABOB/leetcode

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

95 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

leetcode

目錄

No. Title Solution Acceptance Difficulty Frequency
0001 Two Sum Go 50.1% Easy
0002 Add Two Numbers Go, Java 45.5% Medium
0009 Palindrome Number Go, Java 58.8% Easy
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
0023 Merge k Sorted Lists Go, Java 56.1% Hard
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
0061 Rotate List Go, Java 39.4% Medium
0066 Plus One Go, Java 47.2% 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
0082 Remove Duplicates from Sorted List II Go, Java 49.3% Medium
0086 Partition List Go, Java 58.4% 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
0100 Same Tree Go, Java 64.5% Easy
0101 Symmetric Tree Go, Java 58.7% Easy
0104 Maximum Depth of Binary Tree Go, Java 76.8% Easy
0105 Construct Binary Tree from Preorder and Inorder Traversal Go, Java 66.2% Medium
0106 Construct Binary Tree from Inorder and Postorder Traversal Go, Java 65.8% Medium
0108 Convert Sorted Array to Binary Search Tree Go, Java 73.7% Easy
0112 Path Sum Go, Java 52.5% Easy
0114 Flatten Binary Tree to Linked List Go, Java 67.8% Medium
0117 Populating Next Right Pointers in Each Node II Go, Java 55.0% 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
0124 Binary Tree Maximum Path Sum Go, Java 41.0% Hard
0125 Valid Palindrome Go, Java 50.0% Easy
0128 Longest Consecutive Sequence Go, Java 47.2% Medium
0129 Sum Root to Leaf Numbers Go, Java 68.1% 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
0146 LRU Cache Go, Java 44.5% Medium
0148 Sort List Go, Java 61.1% Medium
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
0172 Factorial Trailing Zeroes Go, Java 44.6% Medium
0173 Binary Search Tree Iterator Go, Java 74.4% 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
0222 Count Complete Tree Nodes Go, Java 69.1% Easy
0224 Basic Calculator Go, Java 44.9% Hard
0226 Invert Binary Tree Go, Java 78.6% Easy
0236 Lowest Common Ancestor of a Binary Tree Go, Java 65.9% Medium
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
0427 Construct Quad Tree Go, Java 76.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
}

About

用於記錄 Leetcode 刷題的 Repo

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published