Leetcode Q1 两数之和 Two Sum

题目

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的 两个 整数。

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

  • 示例:

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

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

自解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public int[] TwoSum(int[] nums, int target)
{
if (nums.Length <= 1) return null;

var length = nums.Length;
for (int i = 1; i < length; i++)
{
var a = nums[i - 1];
var index = IsContain(i, target - a, ref nums);
if (index > 0)
{
return new[] {i - 1, index};
}
}

return null;
}

private int IsContain(int _sIndex, int _findNum, ref int[] _targetArray)
{
var length = _targetArray.Length;
for (var i = _sIndex; i < length; i++)
{
if (_targetArray[i] == _findNum) return i;
}

return -1;
}

正解

使用Hashtable Cache住结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int[] TwoSum(int[] nums, int target)
{
if (nums.Length <= 1) return null;

var cache = new Hashtable();
var length = nums.Length;
for (var i = 0; i < length; i++)
{
var need = target - nums[i];
if (cache.ContainsKey(need))
{
return new[] {i, (int) cache[need]};
}

if (!cache.ContainsKey(nums[i]))
{
cache.Add(nums[i], i);
}
}

return null;
}

槽点

  • Hashtable
坚持原创技术分享,您的支持将鼓励我继续创作!