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

翻译

题意：

给定一个数组，这个数组中的两个数字相加等于target，返回这两个数字的序号，并以数组表示。

每组输入都只有一个答案，并且同一数字不能使用两次。

例子：

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

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

我的解法：

import java.util.*;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i = 0;i < nums.length;i ++){
            map.put(nums[i],i);
        }
        for(int i = 0;i < nums.length;i ++)
        {
            int other = target - nums[i];
            if(map.get(other) != null&&map.get(other) != i)
            {
            
                result[0] = i;
                result[1] = map.get(other);
                return result;
            }
        }
        return null;
    }
}

标准解法

解法 1：暴力解法

public int[] twoSum(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[j] == target - nums[i]) {
                return new int[] { i, j };
            }
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}

评论： 双层for循环暴力查找，最简单，但是时间复杂度很大，为O(n^2),空间复杂度为O(1)。

解法 2：Hash 表 两个for循环

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

评论： 根据题意，我们只用求出target和数组中每个数的差值x，并判断的index即可，这里只有查找index最为困难，我们采用Hash表对其进行查找，如果Hash算法选择得当，该查找时间复杂度将为O(1)。

解法 3： Hash 表 单个for循环

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

评论： 根据题意，我们得到的结果中，第一个数的index必定比第二个小，因此，没有必要提前将所有的值压入Map中，可以边查找边压入，因此，可以采用一个for循环完成该操作。