LeetCode - 数组系列 - 两数之和

分手后的思念是犯贱 2023-02-16 05:56 10阅读 0赞

*  题目：两数之和
 *  难度：简单
 *  题目描述：给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
 *  示例：给定 nums = \[2, 7, 11, 15\], target = 9  
    因为 nums\[0\] + nums\[1\] = 2 + 7 = 9  
    所以返回 \[0, 1\]

C语言解法：  
算法总结：暴力遍历寻找两个数的和为目标数，找到存放好返回  
**时间复杂度：O(n \* n)  
空间复杂度：O（n）**  
![在这里插入图片描述][20200608171932620.png]

int* twoSum(int* nums, int numsSize, int target, int* returnSize){ 
    	//nums用于保存传入的数组首地址，
    	//numsSize是传入数组的数据个数
    	//target是2数据的和数，
    	//returnSize用于保存返回的数组中数据的个数
    	int *result = (int*)malloc(sizeof(int)* 2);	
    	//动态开辟一块空间用于存储两个int型数据的数组，并用result指向这块内存
    
    	int i, j;
    	for (i = 0; i < numsSize; i++)
    	{ 
    		for (j = 0; j < numsSize; j++){ 
    			if (i != j){ 
    				if (nums[i] + nums[j] == target){ 	
    				//如果符合两个数之和等于目标数据
    					result[0] = i;		//则存入开辟的空间之中
    					result[1] = j;
    					*returnSize = 2;	
    					return result;
    				}
    				else{ 
    					continue;
    				}
    			}
    		}
    	}
    	return result;		
    	//程序如果走到这里，说明并没有找到两个数据之和为target，
    	//则返回的这个指针，指向的空间中并无数据
    }

Java语言解法：  
算法总结：将数组以<Integer,Integer>的键值对放入HashMap中，然后遍历一遍数组，在HashMap中寻找与target - nums\[i\]差值相等的值，如果找到，则说明可以找到两个值等于target，便将找到的两个值得下标放入一个数组之中作为函数返回值返回  
**时间复杂度：O（n \* n）  
空间复杂度：O（ n ）**  
![在这里插入图片描述][20200608173337525.png]

public static int[] twoSum(int[] nums, int target) { 
            Map<Integer, Integer> m = new HashMap<>();
    
            for (int i = 0; i < nums.length; i++) { 
                m.put(nums[i],i);   //将数组以键值对方式放入HashMap中
                if (m.get(target - nums[i]) != null) { 
                    //如果target - nums[i]在HashMap中找到了相等的值，
                    // 说明找到了这两个值，则将这两个值动态创建成数组返回
                    return new int[]{ m.get(target - nums[i]), i};
                }
            }
            return new int[]{ 0, 0}; //程序运行到这里说明找不到这两个数
        }

[20200608171932620.png]: https://img-blog.csdnimg.cn/20200608171932620.png
[20200608173337525.png]: https://img-blog.csdnimg.cn/20200608173337525.png