之和(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值,若没有在哈希表中找到,则将此值放入哈希表;若找到此值,则直接返回。
更多推荐
两数之和(e)
发布评论