复杂度理论与双指针算法入门

摘要

四个算法的复杂度维度
- 时间复杂度Time complexity
- 空间复杂度Spatial complexity
- 编程复杂度Programming complexity
- 思维复杂度Complexity of thinking
时间复杂度是O(N)的算法有哪些
三种双指针题型
- 背向双指针Back-facing double hands
- 同向双指针Codirectional double pointer
- 相向双指针Opposite double pointer
Valid Palindrome && II
Two Sum型双指针经典题
- 哈希表的做法
- 排序+双指针的做法
- 哈希表与双指针的比较

四个复杂度

时间复杂度 - 核心考察点
空间复杂度 - 次要考察点
编程复杂度 - 能看得懂
思维复杂度 - 能想得出

时间复杂度

P & NP

P问题 Polynomial
- O(n), O(n^2), O(n^3)
- O(n + m), O(√n), O(1)
- O(logn), O(nlogn)
NP 问题 Nondeterministic Polynomial
- O(2^n), O(n^n), O(n!)

常识

只考虑最高项
- O(2^N+N^2) = O(2^N)
- O(N^3+1000N^2) = O(N^3)
不考虑常数项和系数
- O(100N+1000) = O(N)
- O(logN) = O(log(N^2)) = O(log4(N))
O(n+m) 和 O(max(n,m)) 谁更大?
- 相等
- n + m > max (n, m) > (n+m)/2
- O (n+m) > O (max (n, m)) > O ((n+m)/2)
- O(n+m) == O (max (n, m))

时间复杂度为 O(N) 的算法有哪些?

双指针算法
打擂台算法
单调栈算法
单调队列算法
等等

三种双指针算法

背向双指针(最长回文串)
- Longest Palindromic Substring 的中心线枚举算法
- 二分法中的 Find K Closest Elements
相向双指针(判断回文串)
- Reverse 型（题目不多）
  - 翻转字符串
  - 判断回文串
- Two Sum 型（两位数的相关变形题）
  - 两数之和
  - 三数之和
- Partition 型（两位数相关变形题）
  - 快速排序
  - 颜色排序
同向双指针
- 滑动窗口类 Sliding Window
- 快慢指针类 Fast & Slow Pointers

415 · 有效回文串

判断一个字符串忽略大小写和非法字符之后是否是一个回文串

/**
 - @param s: A string
 - @return: Whether the string is a valid palindrome
 */
import "strings"

func IsPalindrome(s string) bool {
    s = strings.ToLower(s)
    i, j := 0, len(s)-1
    for i < j {
        for i < j && !isAlphanumeric(s[i]) {
            i++
        }
        for i < j && !isAlphanumeric(s[j]) {
            j--
        }
        if s[i] != s[j] {
            return false
        }
        i++
        j--
    }
    return true
}

func isAlphanumeric(c byte) bool {
    return (c >= 'a' && c <= 'z') || (c >= '0' && c <= '9')
}

891 · 有效回文串（二）

是否可以在去掉一个字符的情况下是一个回文串

双指针算法。从两头走到中间，发现第一对不一样的字符之后，要么删左边的，要么删右边的。

/**
 - @param s: a string
 - @return: whether you can make s a palindrome by deleting at most one character
 */
func ValidPalindrome(s string) bool {
    left, right := 0, len(s)-1
    for left < right {
        if s[left] != s[right] {
            return isValid(s, left, right-1) || isValid(s, left+1, right)
        }
        left++
        right--
    }
    return true
}

func isValid(s string, left int, right int) bool {
    for left < right {
        if s[left] != s[right] {
            return false
        }
        left++
        right--
    }
    return true
}

56 · 两数之和

哈希表的实现方法

时间复杂度 O(n)
空间复杂度 O(n)

/**
 - @param numbers: An array of Integer
 - @param target: target = numbers[index1] + numbers[index2]
 - @return: [index1, index2] (index1 < index2)
 */
func TwoSum(numbers []int, target int) []int {
    set := make(map[int]int)
    for i, num := range numbers {
        if idx, ok := set[target-num]; ok {
            return []int{idx, i}
        }
        set[num] = i
    }
    return nil
}

排序 + 双指针

时间复杂度 O(nlogn)
空间复杂度 O(1)

import "sort"

/**
 - @param numbers: An array of Integer
 - @param target: target = numbers[index1] + numbers[index2]
 - @return: [index1, index2] (index1 < index2)
 */
func TwoSum(nums []int, target int) []int {
    // 首先对数组进行排序
    sortedNums := make([]int, len(nums))
    copy(sortedNums, nums)
    sort.Ints(sortedNums)

    left, right := 0, len(sortedNums)-1

    // 双指针查找
    for left < right {
        sum := sortedNums[left] + sortedNums[right]
        if sum == target {
            // 在原数组中找到对应的索引
            return findOriginalIndices(nums, sortedNums[left], sortedNums[right])
        } else if sum < target {
            left++
        } else {
            right--
        }
    }
    return nil
}

func findOriginalIndices(nums []int, num1, num2 int) []int {
    indices := make([]int, 2)
    found := 0
    for i, num := range nums {
        if num == num1 || num == num2 {
            indices[found] = i
            found++
            if found == 2 {
                break
            }
        }
    }
    return indices
}

Follow Up 1:

如果输入数据已经排序，哪个算法更好?
双指针的更好，空间复杂度更优

Follow Up 2:

如果需要返回所找的两个数在数组中的下标，哪个算法更好?
哈希表的更好

敬请期待

在后面的直播课程中
我们还将讲解 Two Sum 的“十种”变形题
让你彻底搞定这一类型的相向双指针

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。