题目描述

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

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

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

---

方法和思路解析

方法一（暴力法）：

暴力法比较简单，即遍历每个元素，判断从该元素后是否存在与该元素和为target的元素。两个循环就能搞定。

# solution for python3
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)-1):
            for j in range(i+1, len(nums)):
                sum = nums[i] + nums[j]
                if sum == target:
                    return [i, j]

// solution for c++
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> result;

        for (int i = 0; i < nums.size() - 1; i++){
            for (int j = i + 1; j < nums.size(); j++){
                int sum = nums[i] + nums[j];
                if (sum == target){
                    result.push_back(i);
                    result.push_back(j);
                    break;
                }
            }
        }

        return result;
    }
};

复杂度分析：
其时间复杂度为O(n^2)，空间复杂度为O(1)。

方法二：

第二种是应用首尾递进搜索的方法。如果有一个序列arr是有序的。我们定义两个变量索引head和tail分别指向有序序列的第一个元素和最后一个元素。sum = arr[head] + arr[tail]。将 sum 和 target 相比，如果相等，返回 head 和 tail 索引。如果 sum 小于 target，则head+1后重复求和以及比较流程。如果 sum 大于 target，则tail-1后重复求和以及比较流程。因此，只需要将原定的数组进行排序并记住原来数组索引排序后的位置。接下来就可以应用上述的思路进行。

# solution for python3
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        sorted_id_arr = sorted(range(len(nums)), key=lambda x:nums[x])

        head = 0
        tail = len(nums) - 1

        sum = nums[sorted_id_arr[head]] + nums[sorted_id_arr[tail]]
        
        while sum != target:
            if sum > target:
                tail -= 1
            else:
                head += 1
            
            sum = nums[sorted_id_arr[head]] + nums[sorted_id_arr[tail]]
        
        return [sorted_id_arr[head], sorted_id_arr[tail]]

复杂度分析：
排序复杂度为O(nlog(n))，后续找索引的步骤为O(n)。因此整体时间复杂度为O(nlog(n))。因为创建了索引数组，所以空间复杂度为O(n)。

方法三（两次迭代哈希表法）：

在该方法中，第一次迭代，将每个元素的值和它的索引对{value, index}添加到哈希表中。接着在第二次迭代中，检查每个元素所对应的目标元素（即target减去该元素）是否存在于哈希表中。这里需要注意找到的元素不能是本身。

# solution for python3
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        num_index_dict = {}
        for i in range(len(nums)):
            num_index_dict[nums[i]] = i
        
        for i in range(len(nums)):
            complement = target - nums[i]
            if complement in num_index_dict and num_index_dict[complement] != i:
                return [i, num_index_dict[complement]]

复杂度分析：
两次迭代时间复杂度均为O(n)，所以时间复杂度为O(n)。空间上因为创建了哈希表，所以空间复杂度为O(n)。

方法四（一次迭代哈希表法）：

# solution for python3
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        num_index_dict = {}
        for i in range(len(nums)):
            complement = target - nums[i]
            if complement in num_index_dict:
                return {num_index_dict[complement], i}
            num_index_dict[nums[i]] = i

// solution for c++
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int, int> num_index_map;
        for(int i = 0; i < nums.size(); i++){
            int complement = target - nums[i];
            if (num_index_map.find(complement) != num_index_map.end()){
                int res[] = {num_index_map[complement], i};
                return vector<int>(res, res+2);
            }

            num_index_map[nums[i]] = i;
        }

        return {};
    }
};

复杂度分析：
时间复杂度为O(n)。空间复杂度为O(n)。

---

题目来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。