最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1：

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2：

输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

示例 3：

输入：nums = [1,0,1,2]
输出：3

提示：

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109

解题思路

首先要明白题目的意思，它给了你一个整数的数组，然后需要你找出数组里的最长序列，。先把元素到插入到set里，方便后续的查找操作。后续详细看代码解读。

遇到的问题

1. set集合插入元素吗？

• 提供 O (1) 时间复杂度的查找操作，为后续判断元素是否存在提供高效支持

2. 排序之后怎么找最长连续的序列呢？

• 这里不是先排序，而是遍历集合中的每一个元素。用两个变量：元素起点、序列长度来保存数据，后续的操作都是用来操作他们。简单来说就是循环查找更新变量数值，最后再更新最长序列长度。

3. 为什么不用map而是使用set？

• 因为我们现在只需要判断是否存在而不需要存储键值对的关系；set（或unordered_set）：是 “集合”，仅存储唯一的元素（自动去重）

题解

class Solution {
public:
    int longestConsecutive(vector<int>& nums) { // 接收一个整数数组nums作为输入
        // 找出数组中连续整数组成的最长序列的长度（要求时间复杂度尽可能低）
        unordered_set<int> num_set; // 用无序集合存储数组元素，便于O(1)时间复杂度的查找
        for(const int& num : nums) { 
            num_set.insert(num); // 将数组元素插入集合，自动去重（因为连续序列中重复元素不影响结果）
        }
        int longestStreak = 0; // 定义变量存储最长连续序列的长度，初始化为0

        for(const int& num : num_set) {  // 遍历集合中的每个元素（已去重）
            if(!num_set.count(num - 1)) {  // 核心判断：如果当前元素的前一个数（num-1）不在集合中，说明当前元素是一个连续序列的起点
                int currentNum = num; // 记录当前序列的起点
                int currentStreak = 1; // 记录当前序列的长度，起点本身算1

                while(num_set.count(currentNum +1) ) {  // 循环查找当前序列的下一个元素（currentNum+1）是否存在
                    currentNum += 1; // 若存在，当前数向后移动一位
                    currentStreak += 1; // 当前序列长度加1
                }

                // 更新最长序列长度（取当前最长和历史最长的最大值）
                longestStreak = max(longestStreak, currentStreak);
            }
        }

        return longestStreak; // 返回最长连续序列的长度

        // 排序后找最长连续序列的思路：
        // 1. 先对数组排序（时间复杂度O(n log n)）
        // 2. 遍历排序后的数组，记录当前连续序列长度：
        //    - 若当前元素与前一个元素相等，跳过（去重）
        //    - 若当前元素 = 前一个元素 + 1，当前序列长度+1
        //    - 否则，重置当前序列长度为1
        // 3. 过程中更新最长序列长度
        // 缺点：时间复杂度高于哈希集合方法（哈希法为O(n)）
    }
};

283.移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

思路分析

1. 先理解题目的意思，“不改变非零元素的相对顺序”，非零元素1,3,12的顺序与原数组一致，只有0被移到数组的最后面。
2. 不复制数组的，使用swap交换，代码如下
3. 整体思路就是定义两个指针，一个右指针去遍历，然后一个左指针去准备替换元素。右指针无论是否交换，都会自增1，然循环继续下去。

// 交换两个int类型变量的值
void swap(int& a, int& b) {
    int temp = a;  // 用临时变量保存a的原始值
    a = b;         // 将b的值赋给a
    b = temp;      // 将临时变量中a的原始值赋给b
}

代码解析

class Solution {
public:
    void moveZeroes(vector<int>& nums) { // 给定一个整数数组nums作为输入
    // 编写一个函数将所有0移动到数组的末尾
    // 要求：保持非零元素的相对顺序不变
        int n = nums.size(), left = 0, right = 0; // n为数组长度，left和right为双指针（初始都指向0）
        while(right < n) { // 当右指针未遍历完数组时，继续循环
            if(nums[right]){  // 如果右指针指向的元素不是0（即非零元素）
                swap(nums[left], nums[right]);  // 交换左指针和右指针指向的元素
                left++; // 左指针右移一位，指向下一步待填充的位置
            }
            right++; // 无论是否交换，右指针始终右移一位，继续遍历下一个元素
        }    
    }
};

11.盛水最多的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

示例 1：

输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
示例 2：

输入：height = [1,1]
输出：1

思路分析

首先需要知道，题目意思最终是看什么时候面积最大。不严谨的说，横坐标可以当做长，纵坐标可以看做y。所有首先需要知道面积怎么算min(height[l], height[r]) * (r -l) 。然后就是不断的改变左右指针的值，保存下所有的面积与当前的面积做比较。 最终是返回最大的面积。

class Solution {
public:
    int maxArea(vector<int>& height) { // 这里是接受了一个vector数组的
        int l = 0 ,r = height.size() - 1; // 
        int ans = 0; // 当前的ans是什么？
        while (l < r) {  // 这里的左右方向是不同的 ，从左慢慢靠向右边
            int area = min(height[l], height[r]) * (r -l); // 这里定义一个面积，（r-l）为长度，height为高度
            ans = max(ans, area); // 这里用来保存当前的变量
            if(height[l] <= height[r]) {  // 当左高度小于等于右高度的时候，把左高度悠然
                ++l;
            }
            else {  // 反之 把右指针左移
                --r;
            }
        }
        return ans; // 返回最大的面积
    }
};

这里是每天回答一个问题如果觉得对你有帮助的话，麻烦点一个免费的赞。