算法刷题记录（day1）

 前言 

之前在LeetCode上断断续续刷了几百道题，但是很多题可能过一段时间后又忘了，打算从今天开始尽量保持每天刷题，同时记录下自己的刷题过程和对题目的理解，方便自己进行总结和复习。

LC15.三数之和

题目描述：给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

解题思路：先用sort将数组进行排序（基于快排，时间复杂度O(logn)），遍历数组，首个元素下标为i，若nums[i] > 0，则直接返回。选取i的下一个位置以及数组最后一个位置，根据三个元素之和判断下标移动方式。注意代码里面的去重部分。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;

        sort(nums.begin(), nums.end()); //先从小到大进行排序

        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] > 0) return res;    //第一个大于0，相加不可能为0

            if (i > 0 && nums[i] == nums[i - 1]) continue;  //去重

            int left = i + 1;
            int right = nums.size() - 1;

            while (left < right) {
                if (nums[i] + nums[left] + nums[right] > 0) right--;
                else if (nums[i] + nums[left] + nums[right] < 0) left++;
                else {
                    res.push_back(vector<int>{nums[i], nums[left], nums[right]});
                    while (left < right && nums[left] == nums[left + 1]) left++;    //去重
                    while (left < right && nums[right] == nums[right - 1]) right--; //去重
                    left++;
                    right--;    
                }
            }
        }
        return res;
    }  
};

 LC1.两数之和

题目描述：给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值target的那两个整数，并返回它们的数组下标。

解题思路：使用哈希表解决的经典题目，以数组值为键，下标为值，查找有无满足相加为target的两个数。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> map;
        for (int i = 0; i < nums.size(); i++) {
            auto it = map.find(target - nums[i]);
            if (it != map.end()) return {it->second, i};    //查找到直接返回下标
            map.insert(pair<int, int>{nums[i], i});
        }
        return {};
    }
};

 LC49.字母异位词分组

题目描述：给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

解题思路：利用sort排序，再用哈希表存储有相同字母的元素，相当于用键值对来记录，使用unordered_map，最后遍历哈希表得到输出数组。

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> map;
        
        for (auto& s : strs) {
            string temp = s;
            sort(temp.begin(), temp.end());
            map[temp].push_back(s);
        }

        vector<vector<string>> res;

        for (auto& s : map) {
            res.push_back(s.second);
        }

        return res;
    }
};

 LC128.最长连续序列

题目描述：给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

解题思路：用哈希表记录数组里面的所有值（只记录值，用unordered_set），找到一个连续序列的起始位置（只需要判断当前元素），通过一个循环来记录连续序列的长度，最后和现有的res进行比较，选取最大值。

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> set(nums.begin(), nums.end());
        int res = 0;    //记录输出结果
        for (int i : set) {
            if (!set.count(i - 1)) {    //确保是从i开始的
                int x = i + 1;
                while (set.count(x)) x++;   //记录连续的个数
                res = max(res, x - i);  //记录最大值
            }
        }
        return res;
    }
};