今天早上起來去機房的路上還在想，一直不做算法題老是覺得不踏實。做做題總是讓自己覺得自己真的在做做學習。。。。
這也算是一種強迫症吧。
那就從今天開始做做LeetCode，因為好久沒做過了，所以第一題還是看了別人的題解和思路，算是找找感覺。
總的來說第一題是個水。。。。
Two Sum
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
中文意思就是給你一個整數數組和一個目標值，找出這個數組中的兩個元素的和為該目標值的元素的下標，輸出為index1和index2，按從小到大的序輸出。且假定每個數組都恰好包含一個解，即使，恰好每個給定的數組都有且只有一種符合的結果。
首先，做這種的題目一般都是需要排序的，為了速度，也為了方便查找。
當然，不排序也可以做，，不過那個復雜度貌似有點不合理。
雖然給定的數組不是按序給定的，但是，我們要知道，在這個算法的世界裡面，有序的話，一切都很簡單了。
有序的價值啊。可惜我的生活現在還是有些混亂無章。。。。
但是因為最後要返回的是原數組的元素下標，因此，我們必須要在使用原數組的空間做一個副本。。。。
然後就是打副本，首先假設副本是從小到大，至於怎麼打，我想到一種方法：
選取左右兩個游標，取二者之和，若和等於目標值，將這個所代表的元素在原數組查找確定下標，然後保存在index中。留待返回。
若和大於目標值，則讓右下標往左移；
若和小於目標值，則讓左下標往右移。
直至左右相等之前為止。
因此實現的代碼如下：
/************************************************************************* > File Name: twosum.cpp > Author: SuooL > Mail: [email protected] > Created Time: 2014年07月31日 星期四 20時14分32秒 ************************************************************************/ class Solution { public: vectortwoSum(vector &numbers, int target) { // Note: The Solution object is instantiated only once and is reused by each test case. vector num = numbers; std::sort(num.begin(), num.end()); int length = numbers.size(); int left = 0; int right = length - 1; int sum = 0; vector index; while(left < right) { sum = num[left] + num[right]; if(sum == target) { // find the index from the old array for(int i = 0; i < length; ++i) { if(numbers[i] == num[left]) { index.push_back(i + 1); } else if(numbers[i] == num[right]) { index.push_back(i + 1); } if(index.size() == 2) { break; } } break; } else if(sum > target) { --right; } else { ++left; } } return index; } };
#!/usr/bin/env python
# coding=utf-8
class Solution:
# @return a tuple, (index1, index2)
def twoSum(self, num, target):
numbers = sorted(num)
length = len(num)
left = 0
right = length - 1
index = []
while left < right:
sums = numbers[left] + numbers[right]
if sums == target:
for i in range(length):
if num[i] == numbers[left]:
index.append(i + 1)
elif num[i] == numbers[right]:
index.append(i + 1)
if len(index) == 2:
break
break
elif sums > target:
right -= 1
else:
left += 1
result = tuple(index)
return result
下面的一個類似的解法是網絡上的，用了最新的C++11標准。表示膜拜。
