[LeetCode] 1.Two Sum

1. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

===========大致题目意思================

1.两者求和

有一个整型数组，返回结果依然是数组，元素是给定数组的两个下标，这两个下标对应的元素相加等于一个特定的目标数值

思路一：

1. 需要进行两层for循环；

2. 第二层for循环下标应从第一个for循环下标+1开始，防止重复相加，及自己和自己相加；

3. 条件语句应该是两个元素相加等于目标数字时，获得这两个元素对应的下标放入数组，并返回

实现代码如下：

class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        var resultNums:[Int] = [0, 0]
        
        for i in 0 ..< nums.count {
            for j in i+1 ..< nums.count {
                if nums[i]+nums[j] == target {
                    resultNums[0] = i
                    resultNums[1] = j
                    
                    return resultNums
                }
            }
        }
        
        return resultNums
    }
}

两层for循环好理解但是效率太低，可以使用一层for循环就可以实现 ，运行效率大大提高：

思路二：

1. 定义一个字典，key放数组的元素值，value放下标；

2. 一层for循环记录一个下标；

3. 判断字典中指定目标数减去当前下标对应的元素值的差值为字典的key，看对应的这个key存不存在value

    3.1 若不存在，则将这个元素为key的字典设置value值为当前下标；

    3.2 若存在，则将这个差值为下标对应的字典value值追加到结果数组中，在追加当前下标，再返回目标数据

实现代码如下：

class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        var resultNums:[Int] = []
        var numberDic:[Int : Int] = [:]
        
        for i in 0 ..< nums.count {
            if numberDic[target-nums[i]] != nil {
                resultNums.append(numberDic[target - nums[i]]!)
                resultNums.append(i)
                
                return resultNums
            } else {
                numberDic[nums[i]] = i
            }
        }
        
        return resultNums
    }
}

PS：题目应该注意的点：返回的是下标，而不是下标对应的元素