nSum
LC 1. Two Sum 两数之和
https://leetcode.com/problems/two-sum/
func twoSum(nums []int, target int) []int {
contains := make(map[int]int, len(nums))
for i, num := range nums {
contains[num] = i
}
for j, num := range nums {
if i, exist := contains[target-num]; i != j && exist {
return []int{i, j}
}
}
return nil
}
LC 167. Two Sum II - Input Array Is Sorted 两数之和 II- 输入有序数组
https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/
func twoSum(nums []int, target int) []int {
sort.Ints(nums)
i, j := 0, len(nums)-1
for i < j {
sum := nums[i] + nums[j]
if sum = target {
return []int{nums[i], nums[j]}
} else if sum < target {
i++
} else {
j--
}
}
return nil
}
LC 15. 3Sum 三数之和
https://leetcode.com/problems/3sum/
待复习
func threeSum(nums []int) (results [][]int) {
sort.Ints(nums)
k := 0
for k < len(nums) {
partResults := twoSum(nums[k+1:], -nums[k])
for _, r := range partResults {
results = append(results,
append([]int{nums[k]}, r...),
)
}
for v := nums[k]; k < len(nums) && nums[k] == v; k++ {}
}
return
}
func twoSum(nums []int, target int) (results [][]int) {
i, j := 0, len(nums)-1
for i < j {
sum := nums[i] + nums[j]
if sum == target {
results = append(results, []int{nums[i], nums[j]})
for v := nums[i]; i < len(nums) && nums[i] == v; i++ {}
for v := nums[j]; j >= 0 && nums[j] == v; j-- {}
} else if sum < target {
for v := nums[i]; i < len(nums) && nums[i] == v; i++ {}
} else {
for v := nums[j]; j >= 0 && nums[j] == v; j-- {}
}
}
return
}
LC 18. 4Sum 四数之和
https://leetcode.com/problems/4sum/
待复习
func fourSum(nums []int, target int) (results [][]int) {
sort.Ints(nums)
i := 0
for i < len(nums) - 3 {
j := len(nums) - 1
for i + 2 < j {
partResults := twoSum(nums[i+1:j], target-(nums[i]+nums[j]))
for _, r := range partResults {
results = append(results,
[]int{nums[i], r[0], r[1], nums[j]},
)
}
for v := nums[j]; j > i+2 && nums[j] == v; j-- {}
}
for v := nums[i]; i < len(nums)-3 && nums[i] == v; i++ {}
}
return
}
func twoSum(nums []int, target int) (results [][]int) {
i, j := 0, len(nums)-1
for i < j {
sum := nums[i] + nums[j]
if sum == target {
results = append(results, []int{nums[i], nums[j]})
for v := nums[i]; i < len(nums) && nums[i] == v; i++ {}
for v := nums[j]; j >= 0 && nums[j] == v; j-- {}
} else if sum < target {
for v := nums[i]; i < len(nums) && nums[i] == v; i++ {}
} else {
for v := nums[j]; j >= 0 && nums[j] == v; j-- {}
}
}
return
}
直接利用 3Sum
func fourSum(nums []int, target int) (results [][]int) {
sort.Ints(nums)
i := 0
for i < len(nums) - 3 {
partResults := threeSum(nums[i+1:], target-nums[i])
for _, r := range partResults {
results = append(results,
append([]int{nums[i]}, r...),
)
}
for v := nums[i]; i < len(nums)-3 && nums[i] == v; i++ {}
}
return
}
func threeSum(nums []int, target int) (results [][]int) {
sort.Ints(nums)
k := 0
for k < len(nums) {
partResults := twoSum(nums[k+1:], target-nums[k])
for _, r := range partResults {
results = append(results,
append([]int{nums[k]}, r...),
)
}
for v := nums[k]; k < len(nums) && nums[k] == v; k++ {}
}
return
}
func twoSum(nums []int, target int) (results [][]int) {
i, j := 0, len(nums)-1
for i < j {
sum := nums[i] + nums[j]
if sum == target {
results = append(results, []int{nums[i], nums[j]})
for v := nums[i]; i < len(nums) && nums[i] == v; i++ {}
for v := nums[j]; j >= 0 && nums[j] == v; j-- {}
} else if sum < target {
for v := nums[i]; i < len(nums) && nums[i] == v; i++ {}
} else {
for v := nums[j]; j >= 0 && nums[j] == v; j-- {}
}
}
return
}
nSum
// nums should be already sorted
func nSum(nums []int, target int, n int) (results [][]int) {
if n == 2 {
return twoSum(nums, target)
}
i := 0
for i < len(nums)-n+1 {
partResults := nSum(nums[i+1:], target-nums[i], n-1)
for _, r := range partResults {
results = append(results,
append([]int{nums[i]}, r...),
)
}
for v := nums[i]; i < len(nums)-n+1 && nums[i] == v; i++ {}
}
return
}
func twoSum(nums []int, target int) (results [][]int) {
i, j := 0, len(nums)-1
for i < j {
sum := nums[i] + nums[j]
if sum == target {
results = append(results, []int{nums[i], nums[j]})
for v := nums[i]; i < len(nums) && nums[i] == v; i++ {}
for v := nums[j]; j >= 0 && nums[j] == v; j-- {}
} else if sum < target {
for v := nums[i]; i < len(nums) && nums[i] == v; i++ {}
} else {
for v := nums[j]; j >= 0 && nums[j] == v; j-- {}
}
}
return
}
// 使用示例（利用 4Sum）做演示
func fourSum(nums []int, target int) (results [][]int) {
sort.Ints(nums)
return nSum(nums, target, 4)
}