Week 2 @ 2025 算法周记【nSum + 双指针数组】

1 nSum
2 双指针数组
- 2.1 LC 75. Sort Colors 颜色分类

nSum

LC 1. 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/

待复习

直接利用 3Sum

nSum

双指针数组

LC 75. Sort Colors 颜色分类

https://leetcode.com/problems/sort-colors/

待复习

遍历两次

先把所有 2 移动到最后、再把所有 0 移动到最后

遍历一次