LeetCode题解-Two Sum

比眉伴天荒 2022-05-23 11:41 171阅读 0赞

# LeetCode题解 - 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.  思路一
    
    定义两个指针，一个在数组的最前面，一个在最后面，利用两个循环，一个从前往后走，一个从后往前走。首先，固定前面的指针，后面的指针依次从后往前扫，判断所指数字是不是要找的数字。如果没有找到，前面的指针往前走一步，后面的指针继续从最后面往前扫进行寻找。如此循环，直到找到为止。
2.  思路二
    
    利用字典结构，将数字作为KEY（题目中数字不会重复），数字在数组中的索引作为VALUE。只需要一个循环，从头往后扫，首先判断当前数字是否和字典中存储的KEY之和等于目标值，如果有直接返回即可。如果没有的话，将当前数字加入字典，然后指针前进，继续寻找。
    
    显然，第二种策略效率更高。

## Java实现 ##

第一种实现：

public static int[] twoSum(int[] nums, int target) {
    
        int[] results = new int[2];
        for (int i = 0; i < nums.length; i++) {
            results[0] = nums[i];
            results[1] = target - results[0];
            for (int j = nums.length - 1; j >= 0; j--) {
                if ((nums[j] == results[1]) && (i != j)) {
                    results[0] = i;
                    results[1] = j;
                    return results;
                }
            }
        }
        return null;
    }

第二种实现：

public static int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> dict = new HashMap<>();
        int[] results = new int[2];
        int another;
        for (int i = 0; i < nums.length; i++) {
            another = target - nums[i];
            if (dict.containsKey(another)) {
                results[0] = dict.get(another);
                results[1] = i;
                return results;
            }
            dict.put(nums[i], i);
        }
        return results;
    }

## C++实现 ##

C++版本只给出第二种实现，使用了STL中的`unordered_map`结构。

vector<int> twoSum(vector<int>& nums, int target)
    {
          unordered_map<int, int>  dict;
          vector<int> results = vector<int>(2);
          int another;
          for (int i = 0; i < nums.size(); i ++)
          {
              another = target - nums[i];
              if (dict.find(another) != dict.end())
              {
                  results[0] = dict[another];
                  results[1] = i;
                  return results;
              }
              dict[nums[i]] = i;
          }
        return results;
    }