leetcode刷题日记——两数之和

[ 题目描述 ]：

[ 思路 ]：

• 题目要求 nums 中能够组成和为 target 的两个数的下标
• 解法一：暴力求解，直接两两匹配求解
• 时间复杂度O(n²)，空间复杂度O(1)
  

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

• 解法二：快排+双指针，先对数组进行快速排序，然后利用双指针求出组成 target 的两个数，然后再去遍历原数组，求出这两个数的下标
• 时间复杂度O(Nlogⁿ)，空间复杂度O(n)
  

int cmp(const void *a, const void *b) {return (*(int*)a - *(int*)b);
}int* twoSum(int* nums, int numsSize, int target, int* returnSize) {int left=0,right=numsSize-1;int* res=(int*)malloc(sizeof(int)*2);res[0]=-1,res[1]=-1;int* temp=(int*)malloc(sizeof(int)*numsSize);memcpy(temp, nums, sizeof(int) * numsSize);qsort(temp, numsSize, sizeof(int), cmp);while(left<right){if(temp[left]+temp[right]==target){break;}else if(temp[left]+temp[right]>target){right--;}else{left++;}}for (int i=0; i<numsSize;i++) {if (nums[i]==temp[left] && res[0]==-1) {res[0]=i;} else if(nums[i]==temp[right] && res[1]==-1) {res[1]=i;}if (res[0]!=-1 && res[1]!=-1) break;}*returnSize=2;return res;
}

[ 官方题解 ]：

• 一、暴力枚举，如一
• 二、哈希表：创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配

class Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:hashtable = dict()for i, num in enumerate(nums):if target - num in hashtable:return [hashtable[target - num], i]hashtable[nums[i]] = ireturn []