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;
    }
};