欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode两数之和(c++)

程序员文章站 2022-07-15 12:23:04
...

题目

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/two-sum

分析

  • 法一 先排序再双指针
    先对数组进行一次排序,利用双指针,从一头一尾进行扫描。
  1. 若两数之和等于target,则返回排序前下标。
  2. 若两数之和小于target,则i++。
  3. 若两数之和大于target,则j–。
    按上述步骤依次循环直至两指针相遇或交叉(i==j,i>j)
    tips
    因为排序会丢失原数组下标位置,所以可以设置一个结构体记录元素值和下标,重载结构体的运算符,在排序时按照先按照元素值从小到大排序,再按照下标值从小到大排序。
  • 法二 hash 法
    介绍下c++STL中的map和unordered_map,二者使用方法相同,但是map内部使用的是红黑树,在进行查询某一关键字时,时间复杂度为O(logN),unordered_map内部结构是散列表,时间复杂度为O(1)。
  1. 初始化散列表
  2. 遍历一次数组,在散列表中查找关键字target-nums[i],若查找到并且对应下标不等于i(一个元素不可重复使用),则记录结果返回。

代码

  • 法一
class Solution {
public:
    typedef struct mp{
        int v;
        int pos;
        bool operator <(const mp & a) const{
            bool flag=v<a.v;
            if(!flag&&v==a.v){
                flag=pos<a.pos;
            }
            return flag;
        }
       
        mp(int vv,int p):v(vv),pos(p){
            
        }
    }mp;
    
    //bool cmp(mp & a,mp &b)
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<mp> snums;
        for(int i=0;i<nums.size();i++){
            mp tmp(nums[i],i);
 			snums.push_back(tmp);
        }
        sort(snums.begin(),snums.end());
        int i=0,j=nums.size()-1,sum=0;
        vector<int> res(2);
		while(i<j){
        	if(snums[i].v+snums[j].v==target){
        		res[0]=snums[i].pos;res[1]=snums[j].pos;
        		return res;
			}
			else if(snums[i].v+snums[j].v>target){
        		j--;
			}else{
				i++;
			}
		}
        return res;		
    }
};

  • 法二
class Solution {
public:
    
    //hash 法
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> mp;//使用散列表而不是红黑树
        vector<int> res(2);
        for(int i=0;i<nums.size();i++){
            mp[nums[i]]=i;
        }
        for(int i=0;i<nums.size();i++){
           const int pair=target-nums[i];
            if(mp.find(pair)!=mp.end()&&mp[pair]>i){
               res[0]=mp[pair];
               res[1]=i;
               break; 
            }
        }
		return res;
    }
};

相关标签: LeetCode刷题记录