LeetCode-两数之和

LeetCode 暴力破解 O（n*2）

C版本

int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    int i,j;
    int *result=NULL;
    *returnSize=2;
    for (i=0;i<numsSize-1;i++){
        for(j=i+1;j<numsSize;j++){
            if(nums[i]+nums[j]==target){
                result=(int*)malloc(sizeof(int)*2);
                result[0]=i;
                result[1]=j;
                return result;
            } 
        }
    }
    return result;
}

二分 O（nlogn）

此题相当于是一道搜索题，固定一个数，找另外一个数。

利用指针直接从两头往中间找，可以省一半时间
C版本

int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    int i,j;
    int *result=NULL;
    *returnSize=2;
    for (i=0;i<numsSize-1;i++){
        for(j=numsSize-1;j>i;j--){
            if(nums[i]+nums[j]==target){
                result=(int*)malloc(sizeof(int)*2);
                result[0]=i;
                result[1]=j;
                return result;
            } 
        }
    }
    return result;
}

对撞指针

C版本

int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    int left = 0;
    int right = numsSize - 1;
    while(left < right)
    {
        while(left < right)
        {
            if(nums [left] + nums [right] == target)
            {
                int *ret = (int *)malloc(sizeof(int)*2);
                ret[0] = left;
                ret[1] = right;
                *returnSize = 2;
                return ret;
            }
            left++;
        }
        left = 0; 
        --right;
    }
    *returnSize = 0;
    return NULL;
}

C++版

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        short a=0,b=nums.size();
        for(short j= b ;j>(b>>1);--j)//一次找两个，故外循环行程减半
        {
            for(short i=a;i<(b-a);++i)//找过的不用再判断，故设i=a 
            {
                if(i!=a&&nums[i]==target-nums[a]) return{i,a};
                if(i!=b-a-1&&nums[i]==target-nums[b-a-1]) return{i,b-a-1};
            }
            ++a;//一次内循环比较头尾两个元素，任何一个满足就结束
        }
        return {};
    }
};

排序+双指针法

这里先将数组排序好O（nlogn），再利用双指针法遍历一遍O（n）得到结果。

为了保存下标信息另开了一个数组
时间复杂度O（nlogn），空间复杂度O（n
C++版

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ans;
        vector<int> temp;
        temp=nums;
        int n=temp.size();
       sort(temp.begin(),temp.end());
       int i=0,j=n-1;
       while(i<j){  
           if(temp[i]+temp[j]>target)j--;
          else if(temp[i]+temp[j]<target)i++;
          else break; 
       }
       if(i<j){
      for(int k=0;k<n;k++){
          if(i<n&&nums[k]==temp[i]){
              ans.push_back(k);
              i=n;
          }
         else if(j<n&&nums[k]==temp[j]){
              ans.push_back(k);
              j=n;
          }
          if(i==n&&j==n)return ans;
      }
      }
        return ans;
    }
};

哈希表法

1.算出当前数字和目标数字的差值
2.检查哈希表中是否存在该差值，存在则返回结果
3.不存在的话，作为当前Key值，索引作为value存入哈希表中
C++版

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        std::unordered_map <int,int> hash;
        vector<int> ans;
        for(int i=0;i<nums.size();i++){
            if(hash.find(target-nums[i])!=hash.end()){
                ans.push_back(i);
                ans.push_back(hash[target-nums[i]]);
                return ans;
            }
            hash[nums[i]]=i;
        }
        return ans;
    }
};

C++版

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ans;
       unordered_map<int,int>hashmap;
       for(int i=0;i<nums.size();i++){
           if(hashmap[target-nums[i]]
          &&hashmap[target-nums[i]]!=i+1){
          //防止利用同个元素
               ans.push_back(i);
               ans.push_back(hashmap[target-nums[i]]-1);
               return ans;
           }
        hashmap[nums[i]]=i+1;
        //将hash表对应下标＋1，防止处理下标为0的情况
       }
      
       return ans;
    }
};