合肥金融网站设计,松原网站建设公司,南昌哪里做网站,个人网页空间我给大家第一阶段的最后一道题就到这里了#xff0c;下次得过段时间了。所以这道题简单一点。但是足够经典
下述题目描述和示例均来自力扣#xff1a;两数之和
题目描述 给定一个整数数组 nums 和一个整数目标值 target#xff0c;请你在该数组中找出 和为目标值 target …我给大家第一阶段的最后一道题就到这里了下次得过段时间了。所以这道题简单一点。但是足够经典
下述题目描述和示例均来自力扣两数之和
题目描述 给定一个整数数组 nums 和一个整数目标值 target请你在该数组中找出 和为目标值 target 的那 两个 整数并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返回答案。 示例 示例 1 输入nums [2,7,11,15], target 9
输出[0,1]
解释因为 nums[0] nums[1] 9 返回 [0, 1] 。示例 2 输入nums [3,2,4], target 6
输出[1,2]示例 3 输入nums [3,3], target 6
输出[0,1] Java解法一我反手就是for暴力
其实暴力的思路很简单直接第一个for保存当前数值然后第二个for将除了当前数的其他数全部和这个数试一遍
合适直接返回不合适接着for直到完全不合适返回空数组。
class Solution {public int[] twoSum(int[] nums, int target) {//我反手看见就是暴力//第一个for获取第一个数for (int i 0; i nums.length; i) {//第二个for获取第二个数//i 1是因为不能是同一个数相加得targetfor (int j i 1; j nums.length; j) {//判断是否位目标数if (nums[i] nums[j] target){//为目标数return new int[]{i,j};}}}//这里说明没有符合的答案返回空数组return new int[]{};}
} 可以看出来时间还是花的挺多只超过了23.36%的man这根本没有打败全世界的人啊nononononononononononononononononononononononononononononononononononono
next
Java解法二采用Map集合作为哈希表
map集合的key-value数据结构就真的就是适合这个题吗嗯咋一看这玩意儿和这道题有啥关系。仔细一想呢。
我们需要X Y target 对吧可以知道有X target - Y 对吧那么如果当前取到的X我们又恰好知道Y的存在是不是直接就起飞了。好的ヽ(▽)و确实起飞了bro
采用map集合key用于存储这个数后面的value用于存储他的数组索引然后采用一层for循环每次取到这个值X看一下map里有没有对应Y使他们相加是target有返回两个的value没有加入map集合。这样的话双层for 的O()的时间复杂度就变成了O()了。
class Solution {public int[] twoSum(int[] nums, int target) {//采用Map集合MapInteger,Integer map new HashMap();//进入循环查找for (int i 0; i nums.length; i) {if (map.containsKey(target - nums[i])){//包含取valueInteger value map.get(target - nums[i]);return new int[]{i,value};}else {//不包含将其加入mapmap.put(nums[i], i);}}return new int[]{};}
} 不是我有点无语这玩意儿怎么还有人能比这还快啊不理解不理解t
但是还是提升了50多倍。 C语言解法
/*** Note: The returned array must be malloced, assume caller calls free().*/
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {int* result (int*)malloc(2 * sizeof(int));*returnSize 0;for (int i 0; i numsSize; i) {for (int j 0; j numsSize; j) {if (nums[i] nums[j] target i ! j) {result[0] i;result[1] j;*returnSize 2;return result;}}}return result;
}
结语
结语就是我很烦我又尝试了无数次表面优化了无数次还是不行行吧接收事实了┭┮﹏┭┮
我的意思是最后我又多次尝试抓紧你可是最后还是和你迷失在成长的路里
