两数之和
2021/12/7 6:21:24
本文主要是介绍两数之和,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目
https://leetcode-cn.com/problems/two-sum/
问题重述
给定一个整数数组nums
和一个整数目标值target
,在该数组中找出和为目标值target
的那两个整数,并返回它们的数组下标。只有一个答案
题目分析
题目说只有唯一确定的解(你可以假设每种输入只会对应一个答案
),又能按区间将数组排序,所以想到了双指针。
解题思路
有三种思路,分别是:暴力、双指针、哈希表
先说暴力,双重循环,找到答案后结束。这样写的时间复杂度很高。
再说双指针做法:先将数组按非递减的顺序排好序,左右指针向中间靠拢,当两个指针指向的数字之和等于target
时返回结果;大于target
时右指针左移;小于target
时左指针右移。
最后说下哈希表,我们的目的是找到数组中存在的两个目标元素。每次访问到一个数\(x\)时查询\(target - x\)之前有没有出现过,有的话返回下标,没有的话将\(x\)加入哈希表。
代码 只含核心代码
暴力
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { int i, j; //双重循环 for(i = 0; i < nums.size(); ++i){ for(int j = i + 1; j < nums.size(); ++j){ if(nums[i] + nums[j] == target) return {i, j}; } } return {-1, -1}; } };
双指针 用双指针的前提是有序,一定不能忘记排序
class Solution { public: vector<int> twoSum(vector<int>& num, int target) { //新开一个数组复制原数组 新数组排序后打乱下标,原数组提供下标 vector<int>nums = num; //排序 sort(nums.begin(), nums.end()); int n = nums.size(); //左右双指针 int i = 0, j = n - 1; int sum ; while(i < j) { sum = nums[i] + nums[j]; //满足条件 if(sum == target) { i = nums[i]; j = nums[j]; break; } //之和小于目标值,让左指针右移 if(sum < target) ++ i; //之和大于目标值,让右指针左移 else -- j; } if(i > j) swap(i, j); vector<int> ans(2, -1); //用的很笨的方法在原数组里面查询下标 for(int k = 0; k < n; ++ k) { if(num[k] == i) { ans[0] = k; break; } } for(int k = 0; k < n; ++ k) { if(k == ans[0]) continue; if(num[k] == j) { ans[1] = k; break; } } return ans; } };
哈希表
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 {i, it->second}; } m[nums[i]] = i; } return {}; } };
小结
这是很多人接触力扣的第一题。愿大家满怀热爱、一往无前。
附一张我的提交记录
这篇关于两数之和的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求
- 2024-10-01使用 golang 将ETH账户的资产平均分散到其他账户
- 2024-10-01JWT用户校验课程:从入门到实践
- 2024-10-01Server Component课程入门指南
- 2024-09-30Dnd-Kit学习:新手快速入门指南