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].

暴力法

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

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(偏移量基準)

有offset方便存取值 e.g. -25不能找arr[-25] ,
但是可以找arr[-25-offset] (offset=min 故-25-offset會變正值)

3. 再掃一次填表 若值x,就把他在nums的index填入arr[x-offset]這格

index=0額外記錄成-1,因為calloc初始化陣列全部值都=0,
不設-1看不出0是初始化的0還是index的0

4. 開始找值,首先讀數值a,去HT內找target-a這個值,
   也就是直接存取 arr[target-a-offset] 這格看index多少

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

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.