题目如下:

Given an array of integers, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

用C写一直没过,而且发现网上好像也很少能看到有C版的,过了几天发现支持了JS Lang于是,用JS实现了一版 160ms,这题可以用暴力,但是会超时。如果是C++可以用Hashmap,当然JS没有这些黑魔法,只能用普通的数据结构,以下是我的解题思路。

解题思路:

  1. 创建一个输入数组的反转数组,就是value => key,方便后面根据value来获取key,也就是元素索引
  2. 排序原数组,从小到大,排序可以用二分排
  3. 创建2个指针一个在数组头部,一个在尾部,如果和小于要求输入的值则头部指针向后偏移,否则尾部指针向前移,直到和等于输入值停止
  4. 在第一步创建的数组中,找到对应的元素索引,返回并++

代码如下:

/**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]} two integers in an array, ie: [index1, index2]
 */
var twoSum = function(numbers, target) {
	function compareNumbers(a, b) {
	  return a - b;
	}
	var len = numbers.length;
	var unsortNumbers = [];
	for (var i = 0; i < len; i++) {
		unsortNumbers[i] = numbers[i];
	};
	numbers.sort(compareNumbers);
	var sp = 0;
	var ep = len-1;
	do {
		if(((numbers[sp]+numbers[ep]) > target) && ep > sp) ep--;
		if((numbers[sp]+numbers[ep]) < target && ep > sp) sp++;
	} while ((numbers[sp]+numbers[ep])!= target)

	var output = [];
	for (var i = 0; i < len; i++) {
		if(unsortNumbers[i] == numbers[sp]){
			for (var j = len - 1; j >= 0; j--) 
			{
				if(unsortNumbers[j] == numbers[ep]){
					output = (i > j) ? [++j, ++i] : [++i, ++j];
					break;
				}
			};
			break;
		}
	};
	return output;
};