# Leetcode 1. Two Sum (C/Python3)
- 題目
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
## C
- 範例
```
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
```
暴力法
---
```c=
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
*returnSize=2;
int *ret=(int*)malloc(2*sizeof(int)),i,j,temp;
for(i=0;i<numsSize;i++){
temp=target-nums[i];
for(j=i+1;j<numsSize;j++){
if(temp==nums[j]){
ret[0]=i;
ret[1]=j;
return ret;
}
}
}
return ret;
}
```
Hash Table
---
```c=
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
int max=nums[0],min=nums[0],i;
for(i=1;i<numsSize;i++){
max=max>nums[i]?max:nums[i];
min=min<nums[i]?min:nums[i];
}
int arrsize=max-min+1;
int *HT=calloc(arrsize--,sizeof(int));
HT[nums[0]-min]=-1;
for(i=1;i<numsSize;i++){
HT[nums[i]-min]=i;
}
*returnSize=2;
int *ret=(int*) malloc(2*sizeof(int)),index2;
for(i=0;i<numsSize;i++){
index2=target-nums[i]-min;
if(index2<0||index2>arrsize)continue;
if(HT[index2]){
ret[0]=i;
ret[1]=HT[index2];
if(HT[index2]<0)ret[1]=0;
if(ret[0]==ret[1]){
continue;
}
free(HT);
return ret;
}
}
return 0;
}
```
思路:
1. 掃一次先找max,min
2. 建array大小max-min+1,初始化成0, offset=min(偏移量基準)
:::info
有offset方便存取值 e.g. -25不能找arr[-25] ,
但是可以找arr[-25-offset] (offset=min 故-25-offset會變正值)
:::
3. 再掃一次填表 若值x,就把他在nums的index填入arr[x-offset]這格
:::info
index=0額外記錄成-1,因為calloc初始化陣列全部值都=0,
不設-1看不出0是初始化的0還是index的0
:::
4. 開始找值,首先讀數值a,去HT內找target-a這個值,
也就是直接存取 ==arr[target-a-offset]== 這格看index多少
:::info
target-a-offset要做判斷 <0 或者 >max-min+1(Hash Table的Size) 都要跳過
因為array不能存取負index以及不能存取範圍以外。
:::
5. 找到值就放進ret[0],ret[1],且值不能相同,回傳ret之前記得釋放HT的記憶體空間,最後回傳ret。
- Runtime:4ms~16ms (98.41%~79.66%)
## Python3
```python=
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
dct = {}
for i,v in enumerate(nums):
if target-v in dct :
return [dct[target-v],i]
dct[v]=i
```
Runtime: 44 ms, faster than 85.74% of Python3 online submissions for Two Sum.
Memory Usage: 14.6 MB, less than 13.08% of Python3 online submissions for Two Sum.