力扣刷题DAY4（哈希表+双指针/简单）

一、两数之和

两数之和

方法一：暴力法 class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { vector<int> res; for (int i = 0; i < nums.size(); i++) { for (int j = i + 1; j < nums.size(); j++) { if (nums[i] + nums[j] == target) { res.emplace_back(i); res.emplace_back(j); } } } return res; } };

复杂度分析

时间复杂度：O(N2)，其中 N 是数组中的元素数量。最坏情况下数组中任意两个数都要被匹配一次。

空间复杂度：O(1)。（在最坏情况下，res 中只会存储 2 个元素。）

 方法二：哈希表 class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int, int> m; for (int i = 0; i < nums.size(); i++) { auto it = m.find(target - nums[i]); if (it != m.end()) { return {it->second, i}; } m.insert({nums[i], i}); } return {}; } };

复杂度分析

时间复杂度：O(N)，其中 N 是数组中的元素数量。边建表边查询。空间复杂度：O(N)，其中 N 是数组中的元素数量。主要为哈希表的开销。

查漏补缺：

参考  C++中的unordered_map用法详解

auto it = m.find(target - nums[i]);

按照Key值（target - nums[i]）寻找，若找到返回元素it，再使用 it->first or it->second 查看键值和值；若没找到返回 m.end()；

m.insert({nums[i], i});

unordered_map 没有 insert(key, value) 这样的用法，正确的插入方式是：m[nums[i]] = i;或者 m.insert({nums[i], i});

易错点：

在没找到答案时，要返回 {}；

return {}; // 如果没有找到，返回空 vector  方法三：双指针（仅适用于有序数组） class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { int i = 0, j = nums.size() - 1; while (i != j) { if (nums[i] + nums[j] == target) return {i, j}; else if (nums[i] + nums[j] > target) j--; else i++; } return {}; } };

思路：对于任意升序数组，如果首尾相加＞target，说明尾加任意数都 ＞target，则删去尾（j--）；如果首尾相加 < target，说明首加任意数都 < target，则删去首（i++）。

复杂度分析

时间复杂度：O(N)空间复杂度：O(1) 二、三数之和

三数之和

方法一：双指针 class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { sort(nums.begin(), nums.end()); int l = 0, r = nums.size() - 1; vector<vector<int> > ans; for (int i = 0; i < nums.size() - 2; ++i) { if (i > 0 && nums[i] == nums[i - 1]) continue; // 跳过重复的元素 int l = i + 1, r = nums.size() - 1; while (l < r) { int sum = nums[i] + nums[l] + nums[r]; if (sum == 0) { 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; } else if (sum < 0) { ++l; } else { --r; } } } return ans; } };

复杂度分析

时间复杂度：O(N2)，其中 N 是数组 nums 的长度。（排序是O（NlogN））空间复杂度：O(logN)。我们忽略存储答案的空间，额外的排序的空间复杂度为 O(logN)。然而我们修改了输入的数组 nums，在实际情况下不一定允许，因此也可以看成使用了一个额外的数组存储了 nums 的副本并进行排序，空间复杂度为 O(N)。

优化版本

for (int i = 0; i < len - 2; i++) { if (i > 0 && nums[i] == nums[i - 1]) continue; if(nums[i]+nums[i+1]+nums[i+2]>0) continue; if(nums[i]+nums[len-1]+nums[len-2]<0) continue; int j = i + 1; int k = len - 1; // 剩下都一样

思路：如果这个数跟此后的最小两个数相加都大于0，那么不会出现正确答案； 如果这个数跟最后的最小两个数相加都小于0，那么不会出现正确答案。

三、后移0

移动零

方法一：我的方法（双指针） class Solution { public: int sumzero(vector<int>& nums) { int ze = 0; for (int i = 0; i < nums.size(); i++) { if (nums[i] == 0) ze++; } return ze; } void moveZeroes(vector<int>& nums) { int ze = sumzero(nums); int len = nums.size(); for (int i = 0; i < ze; i++) { for (int j = 0, k = 1; k < len; j++, k++) { if (nums[j] == 0) { int temp = nums[j]; nums[j] = nums[k]; nums[k] = temp; } } } } };

思路：一次遍历把一个0移到最后，那么n个0需要n次遍历。

复杂度分析

时间复杂度：O(N2)空间复杂度：O(1) 方法二：优化版双指针 class Solution { public: void moveZeroes(vector<int>& nums) { int len = nums.size(); if (len == 0) return; int l = 0; for (int r = 0; r < len; r++) { if (nums[r]) { int temp = nums[l]; nums[l] = nums[r]; nums[r] = temp; l++; } } return; } };

思路：

l 左指针：寻找 0 的位置，用于和非零数交换。r 右指针：遍历数组，寻找 第一个非零数，然后交换到 l 位置，保证非零元素的顺序不变。

复杂度分析

时间复杂度：O(N)空间复杂度：O(1)