minisparrow/algorithm-exercise

• 1 array

  • 快慢指针 删除重复元素

  • 双指针，左右夹逼

    • kSum 问题总结

    对于 kSum 这类问题，
    
    如果求的是具体的位置，就不能 sort，因为排序后位置信息就丢失了
    如果求位置，用 HashMap, 求组合本身，用 HashSet 就足够了
    如果求的是组合本身且 k>2, 无论如何，先排序，然后再考虑用双指针或者 HashSet
    twoSumII()可以作为一个通用的底层函数，它往往有两种实现，双指针或者 HashSet(HashMap)
    twoSumII()的 HashSet 实现，比较直观的是两次遍历，可以优化成单次遍历。
    2Sum求的是位置，因此不能 sort。用两轮循环暴力搜索，时间复杂度O(n^2), 空间复杂度 O(1)；如果用一个 HashMap 来缓存位置，时间复杂度可以降低到 O(n)，代价是空间复杂度变为 O(n)。
    
    2Sum II求的是组合本身，nums数组已排好序，因此就不必再排序了，直接用双指针左右夹逼，时间复杂度 O(n)，空间复杂度 O(1)；也可以用 HashSet，时间复杂度 O(n)，空间复杂度 O(n)，并没有比双指针快，却更占内存。因此这题最佳方法是双指针。
    
    3Sum求的是组合本身且 k>2, 先排序，然后用双指针或者 HashSet 两种方法都可以。
    
    4Sum求的是组合本身且 k>2, 先排序，然后用双指针或者 HashSet 两种方法都可以。