Q1：Two Sum

约定不等于承诺〃 2022-01-07 14:41 96阅读 0赞

## 1. Two Sum ##

**官方的链接：[1. Two Sum][]**

**Description ：**

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\].

--------------------

**问题描述**

给定一个整数数组，返回数组中和为数字target的两个元素的下标。 可以假定每个输入target都有一组特定的输出，并且同个元素只使用一次。

**思路**

数组是无序的，比较便捷的方法就是按照k-v(元素-下标)形式将数据元素进行判断和存储，判断差是否在k中有存储，若有，说明存在，否则把元素进行存储。因为只需要扫描一遍，时间复杂度O(n)，空间复杂度O(n)。

[**\[github-here\]**][github-here]

1 public class Q1_TwoSum {
     2     public int[] twoSum(int[] nums, int target) {
     3         if (null == nums || nums.length < 2)
     4             return null;
     5         //保留結果
     6         int[] result = new int[2];
     7         Map<Integer, Integer> resultMap = new Hashtable<Integer, Integer>();
     8         for (int i = 0; i < nums.length; i++) {
     9             //求差
    10             int differ = target - nums[i];
    11             //存在k，说明符合条件
    12             if (resultMap.containsKey(differ)) {
    13                 int tmpResult = resultMap.get(differ);
    14                 if (tmpResult > i) {
    15                     //输出正确的数组下标
    16                     result[0] = i;
    17                     result[1] = tmpResult;
    18                 } else {
    19                     result[0] = tmpResult;
    20                     result[1] = i;
    21                 }
    22                 return result;
    23             } else {
    24                 //k-v存储
    25                 resultMap.put(nums[i], i);
    26             }
    27         }
    28         return null;
    29     }
    30 }

转载于:https://www.cnblogs.com/wpbxin/p/8653735.html

[1. Two Sum]: https://leetcode.com/problems/two-sum/description/
[github-here]: https://github.com/wpbxin/leetcode-algorithm-questions/tree/master/src/com/leetcode/questions