func threeSumSmaller(nums []int, target int) int {
}
func threeSumSmaller(nums []int, target int) int {
// Micropattern: sort, fix nums[i], converge — and count in bulk.
}
func threeSumSmaller(nums []int, target int) int {
// Micropattern: sort, fix nums[i], converge — and count in bulk.
sort.Ints(nums)
count := 0
}
func threeSumSmaller(nums []int, target int) int {
// Micropattern: sort, fix nums[i], converge — and count in bulk.
sort.Ints(nums)
count := 0
for i := 0; i < len(nums)-2; i++ {
left, right := i+1, len(nums)-1
for left < right {
}
}
}
func threeSumSmaller(nums []int, target int) int {
// Micropattern: sort, fix nums[i], converge — and count in bulk.
sort.Ints(nums)
count := 0
for i := 0; i < len(nums)-2; i++ {
left, right := i+1, len(nums)-1
for left < right {
if nums[i]+nums[left]+nums[right] < target {
} else {
right-- // sum too big, shrink it
}
}
}
}
func threeSumSmaller(nums []int, target int) int {
// Micropattern: sort, fix nums[i], converge — and count in bulk.
sort.Ints(nums)
count := 0
for i := 0; i < len(nums)-2; i++ {
left, right := i+1, len(nums)-1
for left < right {
if nums[i]+nums[left]+nums[right] < target {
// If (i,left,right) works, so does (i,left,k) for every k in (left,right].
} else {
right-- // sum too big, shrink it
}
}
}
}
func threeSumSmaller(nums []int, target int) int {
// Micropattern: sort, fix nums[i], converge — and count in bulk.
sort.Ints(nums)
count := 0
for i := 0; i < len(nums)-2; i++ {
left, right := i+1, len(nums)-1
for left < right {
if nums[i]+nums[left]+nums[right] < target {
// If (i,left,right) works, so does (i,left,k) for every k in (left,right].
count += right - left
left++
} else {
right-- // sum too big, shrink it
}
}
}
}
func threeSumSmaller(nums []int, target int) int {
// Micropattern: sort, fix nums[i], converge — and count in bulk.
sort.Ints(nums)
count := 0
for i := 0; i < len(nums)-2; i++ {
left, right := i+1, len(nums)-1
for left < right {
if nums[i]+nums[left]+nums[right] < target {
// If (i,left,right) works, so does (i,left,k) for every k in (left,right].
count += right - left
left++
} else {
right-- // sum too big, shrink it
}
}
}
return count // O(n^2)
}
Tap the left half to go back, the right half to go forward.
Arrow keys or space to navigate · Esc to exit.