两数之和
原题链接：https://leetcode.cn/problems/two-sum/
题目描述
给定一个整数数组 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
- 只会存在一个有效答案
方法一：暴力破解
第一种方法：循环遍历
题目要求在数组中找两个数，这两个数不相等，并且和为目标值。
那么思路就是设置两个循环，从原数组中遍历，判断和是否等于目标值，并判断两数是否相异。
应注意的是，返回的是该元素在数组中的下标，而非元素本身。
这个方法思路很简单，直接上代码
为什么标题叫暴力破解呢？因为从头到尾都循环一遍了，暴力破解就是把每个可能的值都举出来判断一下，比较费时。
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { for (int index1 = 0; index1 < nums.size(); index1++) { for (int index2 = index1 + 1; index2 < nums.size(); index2++) { if (nums[index1] + nums[index2] == target) { return { index1,index2 }; } } } return {}; } };
运行结果
57 / 57 个通过测试用例
执行用时: 296 ms
内存消耗: 9.9 MB
可见，暴力破解的方法，比较费时
方法二：哈希表
哈希表就是一个map容器，一次能存储一个对组，对组的第一个元素为key值，用于索引，第二个元素为value值，是实值。通过.find();的方法，能够查找map容器中的key值，返回一个迭代器，利用间接访问操作符何以获取到实值。
观察暴力破解的代码，可以发现，每次执行外层的for循环，内层的for循环都会从头到尾执行一遍，执行是为了获取符合条件的数据，但该数据被多次取出。
因此，我们需要一种更优秀的方法，能够快速寻找数组中是否存在目标元素。如果存在，我们需要找出它的索引。
使用哈希表，可以将寻找index2的时间复杂度降低到从O(N)降低到O(1)。
如果事先将数据存到map中，检索到符合条件的元素提前退出，免去执行多轮不必要的查找。
也许可以优化时间。
上代码
也可以使用orderedset
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { map<int, int>mp; for (int i = 0; i < nums.size(); i++) { if (mp.find(target - nums[i]) != mp.end()) { return { i,mp.find(target - nums[i])->second }; } mp.insert(make_pair(nums[i], i)); } return {}; } };
运行结果
57 / 57 个通过测试用例
执行用时: 8 ms
内存消耗: 11 MB
如图，使用哈希表后，时间大幅降低。
三数之和
原题链接：https://leetcode.cn/problems/3sum/
题目描述
给你一个整数数组 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
三个指针
先按从小到大排序（从大到小也可以，下面以从小到大排序为例）。
创建三个变量，用于标记三个位置：
- NOW，随循环移动，表示当前循环的位置。
- LEFT，每轮循环重定向到NOW右侧，根据和的情况向右修正位置。
- RIGHT，每轮循环开始时重定向到数组最右端，根据和的情况想左修正位置。
判断三个指针指向的值的和与零的关系：
- 如果和小于零，说明值偏小，LEFT右移
- 如果和等于零，说明值偏大，RIGHT左移
- 如果和等于零，添加到结果数组中，结果数组是一个存储整型数组的数组
代码第一版
听着不难，来写一下吧
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { int left(0), right(0), now(0); vector<vector<int>>result; sort(nums.begin(), nums.end()); for (; now < nums.size() - 1; now++) { left = now++; right = nums.size() - 1; while (nums[left] + nums[right] + nums[now] != 0 && left < right) { if (nums[left] + nums[right] + nums[now] < 0) left++; else right--; } if (nums[left] + nums[right] + nums[now] == 0) result.push_back({ nums[now],nums[left],nums[right] }); } return result; } };
运行结果
看示例，感觉应该能通过
提交之后，出现了问题：在处理[0,0,0,0]时，返回了两遍相同的结果。
原因是上面的代码中，碰到符合条件的就直接添加到结果数组中了。
由于每次会返回三个值，所以当出现四个或以上重复值的时候，这个问题就会出现。
这也是本题比较麻烦的一点：如何去重。
修改后
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { int left(0), right(0), now(0); vector<vector<int>>result = {}; sort(nums.begin(), nums.end()); for (; now < nums.size() - 1; now++) { if (nums[now] > 0) return result; if (now > 0 && nums[now] == nums[now - 1]) { continue; } left = now + 1; right = nums.size() - 1; while (left < right) { if (nums[left] + nums[right] + nums[now] < 0) left++; else if (nums[left] + nums[right] + nums[now] > 0) right--; else { result.push_back({ nums[now], nums[left], nums[right] }); while (right > left && nums[right] == nums[right - 1])right--; while (right > left && nums[left] == nums[left - 1])left--; right--; left++; } } } return result; } };
附上力扣大佬的注释
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> result; sort(nums.begin(), nums.end()); // 找出a + b + c = 0 // a = nums[i], b = nums[left], c = nums[right] for (int i = 0; i < nums.size(); i++) { // 排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组，直接返回结果就可以了 if (nums[i] > 0) { return result; } // 错误去重方法，将会漏掉-1,-1,2 这种情况 /* if (nums[i] == nums[i + 1]) { continue; } */ // 正确去重方法 if (i > 0 && nums[i] == nums[i - 1]) { continue; } int left = i + 1; int right = nums.size() - 1; while (right > left) { // 去重复逻辑如果放在这里，0，0，0 的情况，可能直接导致 right<=left 了，从而漏掉了 0,0,0 这种三元组 /* while (right > left && nums[right] == nums[right - 1]) right--; while (right > left && nums[left] == nums[left + 1]) left++; */ if (nums[i] + nums[left] + nums[right] > 0) { right--; } else if (nums[i] + nums[left] + nums[right] < 0) { left++; } else { result.push_back(vector<int>{nums[i], nums[left], nums[right]}); // 去重逻辑应该放在找到一个三元组之后 while (right > left && nums[right] == nums[right - 1]) right--; while (right > left && nums[left] == nums[left + 1]) left++; // 找到答案时，双指针同时收缩 right--; left++; } } } return result; } };
运行结果
执行用时：120 ms, 在所有 C++ 提交中击败了42.00%的用户
内存消耗：23.3 MB, 在所有 C++ 提交中击败了45.57%的用户
通过测试用例：312 / 312
哈希表
思路跟三个指针、处理两数之和的方法类似，不同的是遍历的方法：由指针换成了表。
但在本题中，并没有表现出更好的性能。
由于这次我们要返回的是值而非下标，因此不需要使用map容器。
以下注释来自力扣大佬的分享。
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> result; sort(nums.begin(), nums.end()); // 找出a + b + c = 0 // a = nums[i], b = nums[j], c = -(a + b) for (int i = 0; i < nums.size(); i++) { // 排序之后如果第一个元素已经大于零，那么不可能凑成三元组 if (nums[i] > 0) { break; } if (i > 0 && nums[i] == nums[i - 1]) { //三元组元素a去重 continue; } unordered_set<int> set; for (int j = i + 1; j < nums.size(); j++) { if (j > i + 2 && nums[j] == nums[j - 1] && nums[j - 1] == nums[j - 2]) { // 三元组元素b去重 continue; } int c = 0 - (nums[i] + nums[j]); if (set.find(c) != set.end()) { result.push_back({ nums[i], nums[j], c }); set.erase(c);// 三元组元素c去重 } else { set.insert(nums[j]); } } } return result; } };
运行结果
超时
共勉
