1. 两数之和

Posted on Edited on In , ,
转载自Leet Code

题目描述

给定一个整数数组nums和一个目标值target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

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

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

我的代码

\(T(N) = O(N^2)\), \(S(n) = O(1)\)

{.line-numbers}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class MySolution
{
    public int[] twoSum(int[] nums, int target) 
    {
    	int i1 = 0; int num1; int i2 = 0; int num2; boolean found = false;
    	
    	for (int i=0; i<nums.length-1; i++)
    	{
            i1 = i; num1 = nums[i];
            for (int j=i+1; j<nums.length; j++)
            {
                i2 = j; num2 = nums[j];
                if (num1+num2==target)
                {
                    found = true; break;
                }
            }
            if (found) break;
    	}
    	int []ans = {i1, i2};
    	return ans;
    }
}

方法一：两遍哈希表

\(T(N) = O(N)\), \(S(N) = O(N)\)

把元素到下标的map放进哈希表。 遍历数组，算出当前元素与target之间的gap，查找该gap是否在map的keySet里。 有的话取出它俩对应的val返回。 (由于哈希表的性质，不会发生返回相同下标的情况。)

{.line-numbers}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution
{
    public int[] twoSum(int[] nums, int target) 
    {
    	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 gap = target-nums[i];
            if (map.containsKey(gap)&&map.get(gap)!=i)
            {
                int []ans = {map.get(gap), i};
                return ans;
            }
    	}
    	return null;
    }
}

方法二: 一遍哈希表

\(T(N) = O(N)\), \(S(N) = O(N)\)

事实证明，我们可以一次完成。 在进行迭代并将元素插入到表中的同时， 我们还会回过头来检查表中是否已经存在当前元素所对应的目标元素。 如果它存在，那我们已经找到了对应解，并立即将其返回。

{.line-numbers}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution
{
    public int[] twoSum(int[] nums, int target) 
    {
    	HashMap<Integer, Integer> map = new HashMap();
    	
    	for(int i=0; i<nums.length; i++)
        {
            int gap = target-nums[i];
            if (map.containsKey(gap)&&map.get(gap)!=i)
            {
                int []ans = {map.get(gap), i};
                return ans;
            }
            // 这句必须在查找gap的后面 避免需要相同元素的情况下返回null
            map.put(nums[i], i);
        }
    	return null;
    }
}