LeetCode两数之和(c++)

题目

给定一个整数数组 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;
    }
};

猜你喜欢