两数之和（e）

之和（e）"/>

两数之和（e）

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

来源：力扣（LeetCode）

C

法一：暴力法

/*** Note: The returned array must be malloced, assume caller calls free().*/
int* twoSum(int* nums, int numsSize, int target, int* returnSize){int *lst = (int*)malloc(sizeof(int) * 2);
lst[0] = 0;lst[1] = 0;
for (int i = 0; i<numsSize - 1; i++)
{for (int j = i + 1; j<numsSize; j++){if (nums[i] + nums[j] == target){lst[0] = i;lst[1] = j;*returnSize = 2;return lst;}}
}
return 0;
}

法二：数组散列法

nums:
元素：
        2,7,11,15
下标：
        0,1,2,3
hash：
元素：
        -1，-1，0，-1，-1，-1，-1，1，-1，-1，-1，2，-1，-1，-1，3
下标：
          0，1，2，3，4，5，6，7，8，9，10，11，12，13，14，15

/*** Note: The returned array must be malloced, assume caller calls free().*/
#define MAX_SIZE 2048
int* twoSum(int* nums, int numsSize, int target, int* returnSize){int i, hash[MAX_SIZE], *res  = (int *)malloc (sizeof(int)*2);memset(hash, -1, sizeof(hash));//对数组进行清零操作for(i=0; i < numsSize; i++){if(hash[(target - nums[i] + MAX_SIZE) % MAX_SIZE] != -1){res[0] = hash[(target - nums[i] + MAX_SIZE) % MAX_SIZE];res[1] = i;*returnSize = 2;return res;}hash[(nums[i] + MAX_SIZE) % MAX_SIZE] = i;//防止负数下标越界，循环散列}free(hash);*returnSize = 0;return res;
}

这种方法局限在数组长度上，空间不够就会导致hash散列冲突

• void *memset(void *s, int ch, size_t n);
• 作用是在一段内存块中填充某个给定的值，它是对较大的结构体或数组进行清零操作的一种最快方法
• memset()函数原型是extern void *memset(void *buffer, int c, int count)       *buffer：为指针或是数组
        c：是赋给buffer的值
        count：是buffer的长度

Java

法一：暴力法

class Solution {public int[] twoSum(int[] nums, int target) {for(int i=0; i<nums.length; i++){for(int j=i+1; j<nums.length; j++){if(nums[i] + nums[j] == target){return new int[]{i,j};}}}throw new IllegalArgumentException("No two sum solution");//非法参数异常//抛出的异常表明向方法传递了一个不合法或不正确的参数}
}

法二：两遍哈希表

class Solution {public int[] twoSum(int[] nums, int target) {Map<Integer,Integer> map = new HashMap<>();for(int i = 0; i<nums.length; i++){map.put(nums[i],i);//nums[i]为key值//i为value值}for(int i = 0; i < nums.length; i++){int complement = target - nums[i];if(map.containsKey(complement) && map.get(complement) != i){//containsKey函数返回true,false;判断key值中是否有complement值//get函数：若存在complement值，则返回complement对应的value值;若不存在complement值，则返回null//map.get(complement) != i 保证同一数字不重复使用return new int[]{i,map.get(complement)};}}throw new IllegalArgumentException("No two sum solution");}
}

法三：一遍哈希表

class Solution {public int[] twoSum(int[] nums, int target) {Map<Integer,Integer> map = new HashMap<>();for(int i = 0; i<nums.length; i++){int complement = target - nums[i];if(map.containsKey(complement)){return new int[]{map.get(complement),i};//先返回已放入hash表中的值，再返回当前值的key}map.put(nums[i],i);}throw new IllegalArgumentException("No two sum solution");}
}

法二：
先将全部数值放入哈希表，再在哈希表中寻找compenent值对应的value值。
法三：
先寻找compenent值对应的value值，若没有在哈希表中找到，则将此值放入哈希表；若找到此值，则直接返回。