查找表的经典题
原创
查找表的经典题
原创
前言
大家好，我是来自「华为」的「程序员小熊」。清明假期到了，小熊给大家带来一道简单题，让大家放松放松。这道题也是各大厂的面试题，例如苹果、脸书、亚马逊和微软等等。
本文主要介绍通过「查找表」的策略来解答此题，同时也会介绍「双指针」中的「对撞指针」方法，供大家参考，希望对大家有所帮助。
两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target
的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1:
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
提示：
2 <= nums.length <= 10^4
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9
只会存在一个有效答案
进阶：你可以想出一个时间复杂度小于 O(n^2) 的算法吗？解题思路
在数组（「不一定有序」）中查找两个元素，使得「其和等于目标值」，求这两个元素的下标。最容易想到的方法是「暴力法」，只需要「枚举」数组中所有的不同的两个元素组合，判断其和是否等于目标值 target 即可。
暴力法
两层遍历数组，找出数组中不同的两个下标，使其对应的元素之和等于目标值 target。
Show me the Code
「C」
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
*returnSize = 0;
int *res = (int *)malloc(sizeof(int) * 2);
if (res == NULL) {
return NULL;
}
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;
}「复杂度分析」
时间复杂度：「O(n^2)」，其中 n 是数组的长度，两层遍历数组。
空间复杂度：「O(1)」，未开辟额外的空间。
哈希表
如果在面试中，只提供「暴力法」的解题思路，面试官往往「不太满意」，会问候选人还有没有「更优的」解题方法；而且本题「进阶」中也提示能否想出一个时间复杂度低于「O(n^2)」 的算法。
可以考虑采用「空间换时间」的策略，来降低时间复杂度。假设待查找的一个元素是 a，则另一个待查找的元素为 target - a，因此在遍历数组时，可以通过「记录 a 和其下标」，并判断「target - a 是否在记录的查找表中」，从而将时间复杂度降到「O(n)」。
「举例」
以数组 nums = [2,7,11,15]，target = 9 为例子，采用「哈希表」的策略，其查找过程如下动图示。
Show me the Code
「C++」
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> record;
for (int i = 0; i < nums.size(); ++i) {
int theOther = target - nums[i];
if (record.find(theOther) != record.end()) {
int res[2] = {i, record[theOther]};
return vector<int>(res, res + 2);
}
record[nums[i]] = i;
}
return {};
}「java」
int[] twoSum(int[] nums, int target) {
int len = nums.length;
Map<Integer, Integer> record = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; ++i) {
int theOther = target - nums[i];
if (record.containsKey(theOther)) {
return new int[]{record.get(theOther), i};
}
record.put(nums[i], i);
}
return new int[0];
}「Python3」
def twoSum(self, nums: List[int], target: int) -> List[int]:
hashtable = dict()
for i, num in enumerate(nums):
theOther = target - num
if theOther in hashtable:
return [hashtable[theOther], i]
hashtable[nums[i]] = i
return []「复杂度分析」
时间复杂度：「O(n)」，其中 n 是数组的长度。在哈希表中查找 target - a 只需要「O(1)」 的时间复杂度。
空间复杂度：「O(n)」，其中 n 是数组中元素个数。主要用于开辟长度为 n 的哈希表。
双指针
如果数组是「有序」的话，了解「双指针」的童鞋，很容易想到可以通过双指针中的「对撞指针」的方法去求解，由于题目没有告知数组是有序的，所以要想使用「对撞指针」，首先得对数组进行「排序」。
排序完成之后，初始化两个指针，其中首指针指向数组第一个元素，尾指针指向数组的最后一个元素，然后判断其指向的「元素之和是否等于目标值」，如果等于，则直接返回两下标，否则「移动首尾指针」（小于目标值，右移首指针；否则，左移尾指针），直至找到。
Show me the Code
「C」
int cmp(const void *a, const void *b) {
return *(int *)a - *(int *)b;
}
/* 对撞指针获取数组中元素之和等于 target 的两元素 */
void getIdxOfNumsByTwoPoints(int *arr, int arrSize, int target, int *l, int *r) {
int left = 0, right = arrSize - 1;
while (left <= right) {
int value = arr[left] + arr[right];
if (value < target) {
left++;
} else if (value > target) {
right--;
} else {
*l = left;
*r = right;
break;
}
}
return;
}
/* 获取第一个元素的下标 */
int obtainIdxFromArr(int *arr, int arrSize, int target) {
for (int i = 0; i < arrSize; ++i) {
if (arr[i] == target) {
return i;
}
}
return -1;
}
/* 获取第二个元素的下标 */
int obtainIdxFromArrNotRepeat(int *arr, int arrSize, int target, int k) {
for (int i = 0; i < arrSize; ++i) {
if (arr[i] == target && i != k) {
return i;
}
}
return -1;
}
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
*returnSize = 0;
int *arr = (int *)malloc(numsSize * sizeof(int));
if (arr == NULL) {
return NULL;
}
/* 拷贝一份 nums 用于排序查找 */
memcpy(arr, nums, numsSize * sizeof(int));
qsort(arr, numsSize, sizeof(int), cmp);
int ret = 0;
int one = 0, theOther = 0;
getIdxOfNumsByTwoPoints(arr, numsSize, target, &one, &theOther);
int *res = (int *)malloc(2 * sizeof(int));
if (res == NULL) {
return NULL;
}
memset(res, -1, sizeof(int) * 2);
res[0] = obtainIdxFromArr(nums, numsSize, arr[one]);
if (res[0] == -1) {
return NULL;
}
res[1] = obtainIdxFromArrNotRepeat(nums, numsSize, arr[theOther], res[0]);
if (res[1] == -1) {
return NULL;
}
*returnSize = 2;
return res;
}「复杂度分析」
时间复杂度：「O(nlogn)」，其中 n 是数组的长度。遍历数组「O(n)」，快排「O(nlogn)」，两者之和还是「O(nlogn)」。
空间复杂度：「O(n)」，其中 n 是数组的长度，开辟了额外空间，用于排序。
往期精彩回顾
更多精彩
关注公众号「程序员小熊」
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
腾讯云开发者
