1 最长连续序列

分析

由于要求时间复杂度为 $O(n)$，同时该题的本质在于查询，哈希表的查询效率就是 $O(1)$ 。因此可以采用哈希表进行查询同时遍历所有值

\begin{algorithm} \caption{longestConsecutive(nums)} \begin{algorithmic} \State 哈希表 used \For{i in nums} \State used[i] = false \Comment{初始化所有索引认为均未遍历} \EndFor \State longest = 0\Comment{设置初始化最大连续长度} \For{i in nums}\Comment{开始遍历全部元素这也是时间复杂度为$O(n)$的原因} \If{used[i]} \Continue\Comment{若被遍历过说明其已找到属于它的最大连续子数组，没有必要再遍历} \EndIf \State length = 1\Comment{初始化最大连续长度} \State used[i] = True\Comment{标记该元素已经被遍历} \State j = i + 1\Comment{开始遍历其右侧的值直至不再连续} \While{j in used.keys} \State used[j] = true \State length += 1\Comment{找到了一个连续的} \State j += 1 \EndWhile \State j = i - 1\Comment{继续寻找i左侧的连续值} \While{j in used.keys} \State used[j] = true \State length += 1 \State j -= 1 \EndWhile \State longest = max(length, longest) \EndFor \Return longest \end{algorithmic} \end{algorithm}

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_map<int, bool> used;  // 创建哈希表
        for (auto i : nums) used[i] = false;
        int longest = 0;
        for (auto i : nums){  // 利用auto i : nums遍历nums中的值
            if (used[i]) continue;
            int length = 1;
            used[i] = true;
            for (int j = i + 1; used.find(j) != used.end(); ++j){
                used[j] = true;
                ++length;
            }
            for (int j = i - 1;used.find(j) != used.end(); --j){
                used[j] = true;
                ++length;
            }
            longest = max(longest, length);
        }
        return longest;
    }
};

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        """
        由于要求O(n)的时间复杂度，可以考虑双指针，但是此处明显无法解决，故考虑其他方式，考虑到哈希表的查询复杂度为O(1)，故可以对于 nums 中的元
        素 x，以 x 为起点，不断查找下一个数 x+1,x+2,⋯ 是否在 nums 中，并统计序列的长度。
        注意若
        - 集合中存在x-1，则不应以x作为起点(这样便无需维护其是否被遍历过)
        """
        hash_set = set(nums)
        max_len = 0
        for i in hash_set:
            if i - 1 in hash_set:
                continue
            y = i + 1
            while y in hash_set:
                y += 1
            max_len = max(max_len, y - i)
        return max_len

2 两数之和

分析

为了尽量使时间复杂度较低，现分析几种方法：

暴力枚举法($C_n^2\to O(n^2)$)
先排序($O(n\log n)$)后夹逼($O(n)$)，最终 $O(n\log n)$
哈希：用一个哈希表，存储每个数对应的下标，复杂度 $O(n)$

该题较为简单暂不书写伪代码😃

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        word_dict = {j: i for i, j in enumerate(nums)}
        for i, j in enumerate(nums):
            # 若某数等于目标值的一半且数组中还有一个相同的值，则可；反之，则否
            if 2 * j == target:
                if i != word_dict[j]: 
                    return [i, word_dict[j]]
                else:
                    continue 
            if target - j in word_dict.keys():
                return [i, word_dict[target-j]]

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> mapping;
        vector<int> result;
        for (int i = 0; i < nums.size(); i++) mapping[nums[i]] = i;
        for (int i = 0; i < nums.size(); i++){
            int gap = target - nums[i];
            if (mapping.find(gap) != mapping.end() && mapping[gap] > i){
                result.push_back(i);
                result.push_back(mapping[gap]);
            }
        }
        return result;

    }
};