文章目录

• 一、数组
• 二、面试高频题

一、数组

研究一个数据结构的时候，首先讲的是它的增删改查功能。

形式：$[1,2,3,4,5]$，可以类比排队的时候根据序号查找某个人。

查找：根据下标找到对应的元素，随机访问的时间复杂度是 O(1)。
增 删 改：新增元素和删除元素的时间复杂度都是 O(n)。

for (int i = 0; i < arr.size(); i ++)  arr[i]

优化：首先想到的是暴力破解，如果题目中要求原地删除即要求 O(1) 的空间复杂度，想到用双指针(快慢指针/左右指针)。

二、面试高频题

LeetCode 26 删除有序数组中的重复项 原题链接

    $(1)$ 排序好的，证明相同的元素是放在一起的；
    $(2)$ 原地删除，证明要求 O(1) 的空间复杂度，想到用双指针（快慢指针）降低时间复杂度；
    $(3)$ 删除重复元素；

// 解法一class Solution {public:    int removeDuplicates(vector<int>& nums) { int slow = 0, fast = 0;; while (fast < nums.size()) {     if (nums[slow] != nums[fast]) nums[++ slow] = nums[fast];     fast ++; } return slow + 1;};

// 解法二class Solution {public:    int removeDuplicates(vector<int>& nums) { int k = 0; for (int i = 0; i < nums.size(); i ++)     if (!i || nums[i] != nums[i - 1]) // !1：第一个元素前面没有数，需要特判  nums[k ++] = nums[i]; return k;    }};

LeetCode 27 移除元素 原题链接

    $(1)$ 原地移除用双指针（快慢指针）；

class Solution {public:    int removeElement(vector<int>& nums, int val) { int slow = 0, fast = 0; while (fast < nums.size()) {     if (nums[fast] != val) nums[slow ++] = nums[fast];     fast ++; } return slow;    }};  

LeetCode 283 移动0 原题链接

• fast 移动到值为非 $0$ 处之后与 $slow$ 指向的数值进行交换；

class Solution {public:    void moveZeroes(vector<int>& nums) { int k = 0; for (int i = 0; i < nums.size(); i ++)     if (nums[i] != 0)   swap(nums[k ++], nums[i]);    }};

 
LeetCode 524. 通过删除字母匹配到字典里最长单词 原题链接

    $(1)$ 两个指针 $i$ 和 $j$ 在两个不同的字符串中进行遍历；
    $(2)$ $i$ 走的快，$j$ 走的慢；

class Solution {public:    bool isMatch(string& s, string& t) { int i = 0;  int j = 0; while (i < s.size() && j < t.size()) {     if (s[i] == t[j]) {  i ++;  j ++;     }else {  i ++;     } } return j == t.size();    }    string findLongestWord(string s, vector<string>& dictionary) { // 两个指针在两个字符串中行走 sort(dictionary.begin(), dictionary.end(), [](auto& a, auto& b) {     if (a.size() == b.size()) return a < b;     return a.size() > b.size(); }); for (int i = 0; i < dictionary.size(); i ++) {     if (isMatch(s, dictionary[i]))     return dictionary[i]; } return "";    }};

LeetCode 删除有序数组中的重复项 II 原题链接

class Solution {public:    int removeDuplicates(vector<int>& nums) { int k = 0; for (auto x : nums)     if (k < 2 || (nums[k - 1] != x || nums[k - 2] != x))  nums[k ++] = x; return k;    }};

LeetCode 167 两数之和II-输入有序数组 原题链接

    $(1)$ 数组有序；
    $(2)$ 只需要找到一对儿两个数之和等于目标值的数对即可；

class Solution {public:    vector<int> twoSum(vector<int>& numbers, int target) { vector<int> ret; int l = 0, r = numbers.size() - 1; while (l < r) {     if (numbers[l] + numbers[r] > target) r --;     else if (numbers[l] + numbers[r] < target) l ++;     else {  ret.push_back(l + 1);  ret.push_back(r + 1);  break;     } } return ret;    }};

 
LeetCode 1679. K 和数对的最大数目 原题链接

    $(1)$ 思路类似于两数之和。

class Solution {public:    int maxOperations(vector<int>& nums, int k) { sort(nums.begin(), nums.end()); int l = 0, r = nums.size() - 1, ret = 0; while (l < r) {     if (nums[l] + nums[r] > k) r --;     else if (nums[l] + nums[r] < k) l ++;     else {  l ++;  r --;  ret ++;     }  }  return ret;    }};

 
LeetCode 面试题 16.24. 数对和 原题链接

    $(1)$ 给原数组进行排序；
    $(2)$ 找到所有对儿两个数之和等于目标值的数对；

class Solution {public:    vector<vector<int>> pairSums(vector<int>& nums, int target) { sort(nums.begin(), nums.end()); int l = 0, r = nums.size() - 1; vector<vector<int>> ret; while (l < r) {     if (nums[l] + nums[r] > target) r --;     else if (nums[l] + nums[r] < target) l ++;     else {  ret.push_back({nums[l], nums[r]});  l ++, r --;     } } return ret;    }};

 
LeetCode 977 有序数组的平方 原题链接

    $(1)$ 原数组是单调递增的；
    $(2)$ 平方数组，以 $0$ 为分界线，左边为递减，右边为递增，两个有序的合并成一个有序的用两路归并；

class Solution {public:    vector<int> sortedSquares(vector<int>& nums) { int n = nums.size(); vector<int> res(n); int left = 0, right = nums.size() - 1, k = n - 1; while (left <= right) {     int l = nums[left] * nums[left];     int r = nums[right] * nums[right];     if (l >= r)      {  res[k --] = l;  left ++;     }     else      {  res[k --] = r;  right --;     } } return res;    }};

LeetCode 209 长度最小的子数组 原题链接

    $(1)$ 暴力解法：每层循环找到一个以 $i$ 开始的大于等于 $target$ 的最短的一个子序列长度，对比完所有的之后得到一个全局的最短的长度（$result$）；
    $(2)$ 双指针解法：不停地调整滑动窗口的大小。$fast$ 每往前走一步，$sum$ 值就更新一下，此时可以通过不停地修改 $slow$ 指针动态地调整滑动窗口的大小。每次更新当前的长度，直到找到一个 $sum$ 小于 $target$，然后再移动 $fast$，每次不停地更新全局的最短的长度（$result$）；

// 暴力解法class Solution {public:    int minSubArrayLen(int target, vector<int>& nums) { int n = nums.size(); int res = n + 1; for (int i = 0; i < nums.size(); i ++) // 起点 {     int sum = 0;     for (int j = i; j < nums.size(); j ++) // 以i为起点的子数组的长度计算     {  sum += nums[j];  if (sum >= target)  {      res = min(res, j - i + 1);      break;  }     } } if (res == n + 1) return 0; return res;    }};

// 双指针解法class Solution {public:    int minSubArrayLen(int target, vector<int>& nums) { // 双指针 int sum = 0; int ret = INT_MAX; for (int i = 0, j = 0; i < nums.size(); i ++) {    // 区间右边界     sum += nums[i];     while (j < i && sum - nums[j] >= target) sum -= nums[j ++];  // (2)     if (sum >= target) ret = min(ret, i - j + 1); } if (ret == INT_MAX) ret = 0;; return ret;    }};

LeetCode 344 反转字符串 原题链接

    $(1)$ 首尾指针，不停地交换首尾指针指向的值；
    $(2)$ 注意结束条件：数组两指针错过（$l$ > $r$）和相等（$l$ == $r$）；

class Solution {public:    void reverseString(vector<char>& s) { int l = 0, r = s.size() - 1; while (l <= r) {     swap(s[l], s[r]);     l ++;     r --; }    }};

LeetCode 349. 两个数组的交集 原题链接

// unordered_set 写法class Solution {public:    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { // 找一个数在哈希表中是否出现过 unordered_set<int> S; vector<int> res; for (int i = 0; i < nums1.size(); i ++) S.insert(nums1[i]); for (int i = 0; i < nums2.size(); i ++)      if (S.count(nums2[i])) {  res.push_back(nums2[i]);  S.erase(nums2[i]);     } return res;    }};

// unordered_map 写法class Solution {public:    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { // 每次找到nums2中第一次在nums1中出现的数 // 出现->哈希表 // 去重 unordered_map<int, int> heap; vector<int> ret; for (int i = 0; i < nums1.size(); i ++) heap[nums1[i]] ++; for (int i = 0; i < nums2.size(); i ++) {     if (heap[nums2[i]] > 0) {  ret.push_back(nums2[i]);  heap.erase(nums2[i]);     } } return ret;    }};