1. 估算算法的时间复杂度的时候一般低于10^7 次操作每秒为佳
    sort 的时间复杂度与编译器具体实现相关，简单考虑成快速排序nlogn

哈希

1.两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。
示例 1：

  • 输入：nums = [2,7,11,15], target = 9
  • 输出：**[0,1]
  • 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

  • 输入：nums = [3,2,4], target = 6
  • 输出：**[1,2]

示例 3：

  • 输入：nums = [3,3], target = 6
  • 输出：[0,1]

提示：

  • 2 <= nums.length <= 104
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109
  • 只会存在一个有效答案

**进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
//map[数，索引]，构建反向索引，便于查找
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> map;
        for(size_t i = 0 ; i < nums.size(); i++){
            if(map.contains(target-nums[i])){
                vector<int> ret;
                ret.push_back(map[target-nums[i]]);
                ret.push_back(i);
                return ret;
            }
            map[nums[i]] = i;
        }
        return vector<int>();
    }
};

2.字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

示例 1:
输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]
解释：
在 strs 中没有字符串可以通过重新排列来形成 “bat”。
字符串 “nat” 和 “tan” 是字母异位词，因为它们可以重新排列以形成彼此。
字符串 “ate” ，”eat” 和 “tea” 是字母异位词，因为它们可以重新排列以形成彼此。

示例 2:
输入: strs = [“”]
输出: [[“”]]
示例 3:
输入: strs = [“a”]
输出: [[“a”]]

提示：
1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i] 仅包含小写字母

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    //排序s，原始序列相同的作为hash表的key
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string,vector<string>> group_strs;
        for(auto& s : strs){
            string sorted_s  = s;
            ranges::sort(sorted_s);
            group_strs[sorted_s].push_back(s);
        }
        vector<vector<string>> ans;
        ans.reserve(group_strs.size());
        for(auto& [_,value] : group_strs){
            ans.push_back(value);
        }
        return ans;
    }
};

3.最长连续序列

给定一个未排序的整数数组 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        //排序+o(n)
        if(nums.size() < 2) return nums.size();
        sort(nums.begin(), nums.end());
        int ans = 1;
        int start = 0;
        int cur = 1;
        for(int i = 1; i < nums.size(); i++)
        {
            if(nums[i] == nums[i - 1])  continue;
            if(nums[i] - nums[i - 1] == 1)
            {
                cur++;
                ans = max(cur, ans);
            }
            else
            {
                start = i;
                cur = 1;
            }
        }
        return ans;
    }
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> num_set;
        for(const int & num : nums){
            num_set.insert(num);
        }
        //也是O(n)
        int longestStreak = 0;
        for(auto& num : num_set){
            if(!num_set.count(num - 1)){
                int currentNum = num;
                int currentStreak = 1;
                while( num_set.count(currentNum + 1)){
                    currentNum += 1;
                    currentStreak += 1;
                }
                longestStreak = max(longestStreak,currentStreak);
            }
        }
        return longestStreak;
    }
};

双指针

4.移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:
输入: nums = [0]
输出: [0]

提示:
1 <= nums.length <= 104
-231 <= nums[i] <= 231 - 1

进阶：你能尽量减少完成的操作次数吗？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        //快指针往前走，往慢指针搬数据，只搬非0值
        //o(n)
        int n = nums.size(),left = 0 , right = 0 ;
        while(right < n){
            if(nums[right]){
                swap(nums[left],nums[right]);
                left++;
            }
            right++;
        }
    }
};

5.盛水最多的容器

给定一个长度为 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

提示：
n == height.length
2 <= n <= 105
0 <= height[i] <= 104

题解：https://leetcode.cn/problems/container-with-most-water/solutions/207215/sheng-zui-duo-shui-de-rong-qi-by-leetcode-solution/?envType=study-plan-v2&envId=top-100-liked
关键：
接水量=两个指针指向的数字中较小值∗指针之间的距离
双指针中靠时，后者减少。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int maxArea(vector<int>& height) {
        int low = 0 , n = height.size(),high = n-1;
        int max_container = 0;
        while(low < high){
            int container = ( high - low ) * min(height[low],height[high]);
            max_container = max(max_container,container);
            if(height[low] < height[high]){
                low++;
            }else{
                high--;
            }
        }
        return max_container;
    }
};

6.三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。

示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

提示：
3 <= nums.length <= 3000
-105 <= nums[i] <= 105

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    //注意不重复指三元组不重复，不是其中的元素不重复，所以每个位置都判断一次即可
    //但是对于第一个元素，如果采用for循环判断，000的情况要注意啊

    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        sort(nums.begin(),nums.end());
        for(int i = 0 ; i < nums.size() - 2; i++ ){
            if(i > 0 && nums[i] == nums[i-1]){
                //核心点，不能使用nums[i] == nums[i+1];会缺失值；仔细对比两者的区别
                continue;
            }
            if(nums[i] > 0){
                break;
            }
            int l = i + 1 , r = nums.size()-1 ;
            while(l < r ){
                int sum = nums[l]+nums[r]+nums[i];
                if(sum < 0){
                    l++;
                }else if(sum > 0){
                    r--;
                }else{
                    ans.push_back({nums[i],nums[l],nums[r]});
                    while(l < r && nums[l] == nums[l+1]){
                        l++;
                    }
                    while(l < r && nums[r] == nums[r-1]){
                        r--;
                    }
                    l++;r--;
                }
            }
        }
        return ans;
    }
};

6.接雨水

定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例 2：
输入：height = [4,2,0,3,2,5]
输出：9

提示：
n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
class Solution {
public:
    int trap(vector<int>& height) {
        //dp
        int total_sum = 0;
        vector<int> dp_l_max;
        vector<int>  dp_r_max;
        dp_l_max.reserve(height.size());
        dp_r_max.reserve(height.size());
        dp_l_max[0] = 0;
        int n = height.size();
        dp_r_max[n-1] = 0;
        for(int i = 0 ; i < height.size() - 1 ; i++)
        {

            dp_l_max[i+1] = max(dp_l_max[i],height[i]);
            dp_r_max[n-i-2] = max(dp_r_max[n-1-i],height[n-i-1]);

        }
        for(int i = 0 ; i < height.size(); i++){
            int max_l = dp_l_max[i], max_r = dp_r_max[i];
            if(max_r > height[i] && max_l > height[i]){
                total_sum += min(max_r,max_l) - height[i];
            }            
        }
        return total_sum;
    }

    int trap(vector<int>& height) {
        //    单调栈存储的是下标，满足从栈底到栈顶的下标对应的数组 height 中的元素递减
        int ans = 0;
        stack<int> stk;
        int n = height.size();
        for (int i = 0; i < n; ++i) {
            while (!stk.empty() && height[i] > height[stk.top()]) {
                int top = stk.top();
                stk.pop();
                if (stk.empty()) {
                    break;
                }
                int left = stk.top();
                int currWidth = i - left - 1;
                int currHeight = min(height[left], height[i]) - height[top];
                ans += currWidth * currHeight;
            }
            stk.push(i);
        }
        return ans;
    }

    int trap(vector<int>& height) {
        //  双指针 存水量只取决于短的柱子 只只关心两者中的较小值，是不是所以没有遍历到的最大值不影响
       int n = height.size();
       if (n<=2)   return 0;
       int l=0,r=n-1;
       int leftmax=height[l], rightmax=height[r];
       int res=0;
       while (l<r) {
           if (leftmax < rightmax) {
               res += leftmax-height[l];
               l++;
               leftmax = max(height[l], leftmax);
           }
           else {
               res += rightmax-height[r];
               r--;
               rightmax = max(height[r], rightmax);
           }
       }
       return res;
   }

};

滑动窗口

1.区分是固定长度的窗口还是非固定长度的窗口，非固定长度窗口参照7.的模板
2.字符串比较的不考虑顺序时可以采用字典集的方式降低时间复杂度
3.如果字符串中包含负数，如第9题，可能导致窗口伸缩状态不确定，这种情况滑动窗口不适用

7. 无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。

示例 1:
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。注意 “bca” 和 “cab” 也是正确答案。

示例 2:
输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

示例 3:
输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。

提示：
0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        ////外层循环扩展右边界，内层循环扩展左边界
        unordered_set<char> char_sets;
        int maxlength = 0;
        int curlength = 0;
        for(int l = 0, r = 0; r < s.length();r++){
            while(l < r && char_sets.contains(s[r])){
                char_sets.erase(s[l]);
                l++;
                curlength -- ;
            }
            char_sets.insert(s[r]);
            curlength++;
            maxlength = max(maxlength,curlength);
        }
        return maxlength;
    }
};

8.找到字符串中所有字母异位词

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

示例 1:
输入: s = “cbaebabacd”, p = “abc”
输出: [0,6]
解释:
起始索引等于 0 的子串是 “cba”, 它是 “abc” 的异位词。
起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。

示例 2:
输入: s = “abab”, p = “ab”
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 “ab”, 它是 “ab” 的异位词。
起始索引等于 1 的子串是 “ba”, 它是 “ab” 的异位词。
起始索引等于 2 的子串是 “ab”, 它是 “ab” 的异位词。

提示:
1 <= s.length, p.length <= 3 * 104
s 和 p 仅包含小写字母

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        //本方法比较时的时间复杂度时o(26)如果排序则复杂度为o(pn)，都很大
        int sLen = s.size(), pLen = p.size();
        if (sLen < pLen) {
            return vector<int>();
        }
        vector<int> ans;
        vector<int> sCount(26);
        vector<int> pCount(26);
        for (int i = 0; i < pLen; ++i) {
            ++sCount[s[i] - 'a'];
            ++pCount[p[i] - 'a'];
        }

        if (sCount == pCount) {
            ans.emplace_back(0);
        }

        for (int i = 0; i < sLen - pLen; ++i) {
            --sCount[s[i] - 'a'];
            ++sCount[s[i + pLen] - 'a'];

            if (sCount == pCount) {
                ans.emplace_back(i + 1);
            }
        }

        return ans;
    }
};

字符串

9.和为 k 的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。

示例 1：
输入：nums = [1,1,1], k = 2
输出：2

示例 2：
输入：nums = [1,2,3], k = 3
输出：2

提示：
1 <= nums.length <= 2 * 104
-1000 <= nums[i] <= 1000
-107 <= k <= 107

前缀合+哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
//滑动窗口不适用负数
    int subarraySum(vector<int>& nums, int k) {
        int ans = 0;
        unordered_map<int,int> prefix_sum_count_map;
        prefix_sum_count_map[0] = 1;//记得初始化0的位置
        int cur_prefix_sum = 0;
        for(int i = 0 ; i < nums.size();i++){
            cur_prefix_sum += nums[i];
            if(prefix_sum_count_map.contains(cur_prefix_sum - k)){
                ans += prefix_sum_count_map[cur_prefix_sum-k];
            }
            if(prefix_sum_count_map.contains(cur_prefix_sum)){
                prefix_sum_count_map[cur_prefix_sum]++;
            }else{
                prefix_sum_count_map[cur_prefix_sum] = 1;
            }
        }
        return ans;
    }
};

10.滑动窗口中的最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。

示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值

[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7

示例 2：
输入：nums = [1], k = 1
输出：[1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    string minWindow(string s, string t) {
        //滑动窗口，右指针找到满足的子串，左指针收缩找到最短的子串
        unordered_map<char,int> need_map,cur_wind_map;
        for(auto& c : t){
            need_map[c]++;
        }
        int r= 0  , l = 0;
        int valid = 0;
        int minLen = INT_MAX, start = 0;

        for(;r < s.size();r++){
            if(need_map.contains(s[r])){
                cur_wind_map[s[r]]++;
                if(cur_wind_map[s[r]] == need_map[s[r]]){
                    valid++;
                }
            }
            while(valid == need_map.size()){
                if(r - l < minLen){
                    minLen = r + 1 - l;
                    start = l;
                }
                if(need_map.contains(s[l])){                        
                    if(cur_wind_map[s[l]] == need_map[s[l]]){
                        valid--;
                    }
                    cur_wind_map[s[l]]--;
                }
                l++;
            }
        }
        if(minLen == INT_MAX){
            return "";
        }
        return s.substr(start,minLen);
    }
};

普通数组

11.最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组是数组中的一个连续部分。

示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：
输入：nums = [1]
输出：1

示例 3：
输入：nums = [5,4,-1,7,8]
输出：23

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        vector<int> dp;
        dp.reserve(nums.size());
        dp[0] = nums[0];
        int max_sum = dp[0];
        for(int i = 1 ; i < nums.size(); i++){
            dp[i] = max(dp[i-1]+nums[i],nums[i]);
            max_sum = max(max_sum,dp[i]);
        }
        return max_sum;
    }
};

12.合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

示例 3：
输入：intervals = [[4,7],[1,4]]
输出：[[1,7]]
解释：区间 [1,4] 和 [4,7] 可被视为重叠区间。

提示：

1 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 104

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if(intervals.size() == 0){
            return {};
        }
        sort(intervals.begin(),intervals.end());
        vector<vector<int>> merged;
        for(int i = 0 ; i < intervals.size() ; i++){
            int l = intervals[i][0], r = intervals[i][1];
            if(merged.empty()){
                merged.push_back({l,r});
            }else{
                if(merged.back()[1] < l){
                    merged.push_back({l,r});
                }else{
                    merged.back()[1] = max(merged.back()[1],r);
                }
            }
        }
        return merged;
    }
};

13.轮转数组

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

示例 2:
输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

提示：
1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
0 <= k <= 105

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    void reverse(vector<int>& nums ,int start,int end){
        while(start < end){
            swap(nums[start],nums[end]);
            start++;
            end--;
        }
    }
    void rotate(vector<int>& nums, int k) {
        k %= nums.size();
        reverse(nums,0,nums.size()-1);
        reverse(nums,0,k-1);//易错
        reverse(nums,k,nums.size()-1);
    }
};
手撕 Leetcode
分享文章

快来参与讨论吧~

本站由 Zane Jiang 使用 Stellar 1.33.1 主题创建，一款很棒的 Hexo 主题！

总访问 次 || 本页访问 次
总访客 人 || 本页访客 人