开学后忙的焦头烂额（懒得很），正式开始刷leecode的题目了。
想了想c语言是最最基础的语言，虽然有很多其他语言很简单，有更多的函数可以用，但c语言能煅炼下自己的思考能力。python则是最流行的语言。
做题用的是 xcode的 leecode插件 非常的方便。顺序从简单到难。开始。
int* twoSum(int* nums, int numsSize, int target) {
int i,j,count=;//count为统计的次数
int *a = (int*)malloc(*sizeof(int));//为a分配内存
//循环遍历数组
for(i=;i<numsSize;i++){
for(j=i+;j<numsSize;j++){
if(nums[i]+nums[j]==target){
a[]=i;
a[]=j;
count=;//统计次数设为1
}
}
if(count==) break; //若找到，则退出。
}
return a;
}
这里有两个点要注意：
1.要对返回的数组进行动态的分配内存，不然会报错。
2.设置一个count，记录是否找到成功的值，找到一次后因为题目要求不能重复利用，其实就可以退出了。
这道题用c语言做可以通过，但是时间复杂度达到了O(n²) 有另一种办法就是用哈希表，在别的一些高级脚本语言中可以用字典的方式，只需要一次遍历就可以。
但是c语言中需要自己写哈希表的东西。这里顺便复习下数据结构的哈希表
参考：https://blog.csdn.net/hang404/article/details/84764531
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
struct node {
long val;
int index;
struct node* next;
};
void insert(struct node** hashTable, long val, int index, int n) {
int t = abs(val) % n;
struct node* temp = hashTable[t];
// head-add
struct node* add = (struct node*)malloc(sizeof(struct node));
add->val = val;
add->index = index;
add->next = temp->next;
temp->next = add;
}
int search(struct node** hashTable, long target, int n) {
int index = abs(target) % n;
struct node* temp = hashTable[index]->next;
while(temp) {
if(temp->val == target) {
return temp->index;
}
temp = temp->next;
}
return -;
}
void freeHashTable(struct node** hashTable, int n) {
int i = ;
struct node *temp = NULL, *delete = NULL;
for(i = ; i < n; i++) {
temp = hashTable[i];
delete = temp;
while(temp) {
delete = temp;
temp = temp->next;
free(delete);
}
}
free(hashTable);
}
int* twoSum(int* nums, int numsSize, int target) {
int i = , j = ;
int n = numsSize, index = ;
int* result = NULL;
struct node** hashTable = (struct node**)malloc(n * sizeof(struct node*));
// init head node
for(i = ; i < n; i++)
hashTable[i] = (struct node*)calloc(, sizeof(struct node));
for(i = ; i < n; i++) {
index = search(hashTable, target - nums[i], n);
if(- == index)
insert(hashTable, nums[i], i, n);
else {
result = (int*)malloc(sizeof(int) * );
result[] = index;
result[] = i;
freeHashTable(hashTable, n);
return result;
}
}
freeHashTable(hashTable, n);
return result;
}
关于哈希表的概念和c语言中哈希表的设计：
https://blog.csdn.net/qq_34888036/article/details/80880487
------------------------------------------------------------------------------------------------------------------------------------------------------------
python：
#
# @lc app=leetcode.cn id=1 lang=python3
#
# [1] 两数之和
#
# https://leetcode-cn.com/problems/two-sum/description/
#
# algorithms
# Easy (44.78%)
# Total Accepted: 257.1K
# Total Submissions: 574K
# Testcase Example: '[2,7,11,15]\n9'
#
# 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
#
# 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
#
# 示例:
#
# 给定 nums = [2, 7, 11, 15], target = 9
#
# 因为 nums[0] + nums[1] = 2 + 7 = 9
# 所以返回 [0, 1]
#
#
#
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
n = len(nums) #获取nums的长度
d = {} #创建空字典
for x in range(n):
a = target - nums[x] #构成target和需要的差值
if nums[x] in d:
return d[nums[x]],x #返回两个位置
else:
d[a]=x #将当前位置所需的差值和自身位置存入字典中
这段代码我还理解了很多遍。
比如从2开始，字典对2的存储是： 7：0
就是当前位置需要的差值，和自身的位置。
然后寻找到下一个 a此时等于2，如果字典中没有这个7的话，那字典中存储的就应该是 2 ：1 也就是它需要2可以合成target，自身的位置是1。
如果有这个7的话，那么就返回 需要差值是7的那个数的位置，和当前位置也就是x。返回的就是 d[7]和1 也就是 0和1
大意就是 从这段数组中，边存便检查，字典中存放target与每个数的差值和自身的位置，在后面如果查找到当前的数和字典中的差值相等，就返回
字典中对应的位置和自身的位置。没查到的话，就把当前数所需差值和当前的位置存放到字典中。