...
| Code Block |
|---|
// nums should be already sorted func nSum(nums []int, target int, n int) (results [][]int) { } |
双指针数组
LC 75. Sort Colors 颜色分类
https://leetcode.com/problems/sort-colors/
...
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)
} |
双指针数组
LC 75. Sort Colors 颜色分类
https://leetcode.com/problems/sort-colors/
| Status | ||||
|---|---|---|---|---|
|
遍历两次
先把所有 2 移动到最后、再把所有 0 移动到最后
| Code Block | ||
|---|---|---|
| ||
func sortColors(nums []int) {
i, j := 0, len(nums)-1
for i <= j {
if nums[i] == 2 {
nums[i], nums[j] = nums[j], nums[i]
j--
} else {
i++
}
}
i=0
for i <= j {
if nums[i] == 1 {
nums[i], nums[j] = nums[j], nums[i]
j--
} else {
i++
}
}
} |
遍历一次
| Code Block | ||
|---|---|---|
| ||
func sortColors(nums []int) {
p0, p2 := 0, len(nums)-1
p := 0
for p <= p2 {
if nums[p] == 0 {
nums[p0], nums[p] = nums[p], nums[p0]
p0++
} else if nums[p] == 2 {
nums[p], nums[p2] = nums[p2], nums[p]
p2--
} else {
p++
}
if p < p0 {
p = p0
}
}
} |