01 相向双指针

1 两数之和

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

1.1 暴力做法

点击查看代码

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

复制代码

- 时间复杂度：$$O(n^2)$$- 空间复杂度：$$O(1)$$1.2 优化搜索

1.2.1 改变原数组（对应提示2）

似乎可以这样。
如果说，对元素从小到大排序，然后就可以使用相向双指针加速搜索。
但是这道题要求返回元素的下标，而原地排序的话就会导致我们不知道当前遍历到的这个元素，之前的下标是谁。
因此，可以考虑将每个下标所对应的元素捆绑起来，在C++中对应的数据结构可以是pair。
点击查看代码

1. class Solution {
2. public:
3.     vector<int> twoSum(vector<int>& nums, int target) {
4.         vector<pair<int, int>> nums_copy; // index value
5.         int n = nums.size();
6.         for (int i = 0; i < n; ++i) { // O(n)
7.             nums_copy.push_back({i, nums[i]});
8.         }
9.         auto compare = [](auto& lhs, auto& rhs) -> bool {
10.             return lhs.second < rhs.second;
11.         };
12.         sort(nums_copy.begin(), nums_copy.end(), compare); // O(nlogn)
13.         int left = 0, right = n - 1;
14.         while (left < right) { // O(n)
15.             int s = nums_copy[left].second + nums_copy[right].second - target;
16.             if (s > 0) {
17.                 --right;
18.             } else if (s < 0) {
19.                 ++left;
20.             } else {
21.                 return {nums_copy[left].first, nums_copy[right].first};
22.             }
23.         }
24.         return {-1, -1};
25.     }
26. };

复制代码

• 时间复杂度：$$O(nlogn)$$
  
• 空间复杂度：$$O(n)$$
  

1.2.2 哈希表

点击查看代码

1. class Solution {
2. public:
3.     vector<int> twoSum(vector<int>& nums, int target) {
4.         // 不改变数组，用哈希表加速搜索
5.         unordered_map<int, int> hash_table;
6.         int n = nums.size();
7.         for (int i = 0; i < n; ++i) {
8.             int x = target - nums[i];
9.             if (hash_table.contains(x)) {
10.                 return {i, hash_table[x]};
11.             } else {
12.                 hash_table[nums[i]] = i;
13.             }
14.         }
15.         return {-1, -1};
16.     }
17. };

复制代码

- 时间复杂度：$$O(n)$$- 空间复杂度：$$O(n)$$思考题

• 如果 nums 是有序的，是否还需要哈希表？换句话说，能否做到 \(O(1)\) 额外空间？
  答：不需要。通过先对数组从小到大排序，进而采用相向双指针即可。
  
• 如果要求寻找三个数，它们的和等于 target 呢？
  

2 三数之和

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

• 根据提示1，我们意识到可以枚举x，这样问题就变成，对于固定的数x，能否找到y和z，使得两数之和等于target - x;
  
• 根据提示2，或许应该对数组进行排序（改变原数组）；
  
• 提示3，不改变原数组，利用类似哈希表的结构加速搜索？
  
• 注意：这道题要求对符合条件的三元组进行去重的操作。
  

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！