[每日一道小算法（八十三）] [迭代] 两数之和（leetCode题）

分手后的思念是犯贱 2023-07-17 14:00 25阅读 0赞

前言：  
最近在学习go语言，所以以后做算法题都会提供两种题解，java和go。并不打算放弃java，语言都是相通的，重要的还是思路。

### 题目描述 ###

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

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:
    
    给定 nums = [2, 7, 11, 15], target = 9
    
    因为 nums[0] + nums[1] = 2 + 7 = 9
    所以返回 [0, 1]

### 解题思路 ###

这道题如果不考虑时间复杂度，我们可以直接使用暴力的方法来求解，我们遍历每个元素 x，并查找是否存在一个值与 target - x相等的目标元素。这样的时间复杂度为O（n2），空间复杂度为O（1）。有没有更好的方法来解决这个问题呢，我们可以使用哈希表来解决这个问题。在进行迭代并将元素插入到哈希表中的同时，我们还会回过头来检查哈希表中是否已经存在当前元素所对应的目标元素。如果它存在，那我们已经找到了对应解，并立即将其返回。这样时间复杂度就变为O（n），空间复杂度为O（n）。这就属于以空间换时间来提高效率。如果不懂的话，看代码，直接能看懂。

### 代码样例 ###

#### golang ####

func twoSum(nums []int, target int) []int{ 
    	m := make(map[int]int,10)
    	for i,v :=range nums{ 
    		k,ok:=m[target-v]
    		if ok{ 
    			return []int{ k,i}
    		}
    		m[v] = i
    	}
    	return nil
    }

#### java ####

class Solution { 
        public int[] twoSum(int[] nums, int target) { 
            Map <Integer,Integer> map = new HashMap<>();
            for(int i=0;i<nums.length;i++)
            { 
                int tmp=target-nums[i];
                if(map.containsKey(tmp))
                { 
                    return new int[] { map.get(tmp),i};
                }
                map.put(nums[i],i);
            }
          throw new IllegalArgumentException("No two sum solution");
        }
    }