莆田专业网站建设公司价格,做得好的网站建设公司,平面设计培训内容,wordpress oauth qq文章目录1. 题目2. 解题2.1 排序双指针2.2 哈希map1. 题目
设计一个算法#xff0c;找出数组中两数之和为指定值的所有整数对。一个数只能属于一个数对。
示例 1:
输入: nums [5,6,5], target 11
输出: [[5,6]]示例 2:
输入: nums [5,6,5,6], target 11
输出: [[5,6],[5…
文章目录1. 题目2. 解题2.1 排序双指针2.2 哈希map1. 题目
设计一个算法找出数组中两数之和为指定值的所有整数对。一个数只能属于一个数对。
示例 1:
输入: nums [5,6,5], target 11
输出: [[5,6]]示例 2:
输入: nums [5,6,5,6], target 11
输出: [[5,6],[5,6]]提示
nums.length 100000来源力扣LeetCode 链接https://leetcode-cn.com/problems/pairs-with-sum-lcci 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
2.1 排序双指针
时间复杂度O(nlogn)O(n \log n)O(nlogn)
class Solution {
public:vectorvectorint pairSums(vectorint nums, int target) {sort(nums.begin(), nums.end());int i 0, j nums.size()-1;vectorvectorint ans;while(i j){if(nums[i]nums[j] target)ans.push_back({nums[i],nums[j--]});else if(nums[i]nums[j] target)i;elsej--;}return ans;}
};308 ms 45.9 MB
2.2 哈希map
2次扫描时间复杂度O(n)O(n)O(n)
class Solution {
public:vectorvectorint pairSums(vectorint nums, int target) {unordered_mapint,int m;for(int n : nums)m[n];vectorvectorint ans;for(int i 0; i nums.size(); i){if(m[nums[i]] m[target-nums[i]]){if((nums[i] target-nums[i]) m[nums[i]] 1)continue;//相等情况需要数量大于等于2ans.push_back({nums[i],target-nums[i]});m[nums[i]]--;m[target-nums[i]]--;}}return ans;}
};356 ms 59.8 MB
优化上面哈希法只需一次扫描
class Solution {
public:vectorvectorint pairSums(vectorint nums, int target) {unordered_mapint,int m;vectorvectorint ans;for(int i 0; i nums.size(); i){if(m[target-nums[i]] 0){ans.push_back({nums[i],target-nums[i]});m[target-nums[i]]--;}elsem[nums[i]];}return ans;}
};316 ms 59.8 MB
